Health policy support in least developing countries is needed to allocate scarce resources most efficiently and produce the maximum health at given resources. However, planners frequently face severe uncertainty of biological, economic and health service structures and parameters. This paper presents a model of cervical cancer (CUC) in Cambodia as an example of health policy support under extreme uncertainty. The projections are based on a multi-compartment dynamic policy model, specifically developed for CUC in Cambodia. The model simulates the demographic system and infections through sexual intercourse for 100 years. Data were taken from the literature and adjusted for Cambodia through interviews. CUC is an increasing problem in Cambodia and the number of deaths due to cervical cancer growths faster than the population. On average, Cambodia will lose some 5159 years of life per year due to CUC. From the alternative interventions against CUC, a “see-and-treat” approach based on VIA screening of women 30–49 years every 3 years seems to be most efficient. The results of the simulation indicate that the “see-and-treat” approach should be implemented in Cambodia. Even under strong changes of parameters and assumptions, this finding is robust. The model is currently being used in development planning. The example shows that health policy support is possible even under extreme uncertainty if the model builder employs a sufficient number of sensitivity analyses and scenarios.