OBJECTIVES: Cervical cancer is the second highest incidence of female cancers in Malaysia. This can be avoided by Pap smear screening and Human Papillomavirus (HPV) vaccination i.e. the bivalent vaccine (BV) and quadrivalent (QV). Three programs cost effectiveness (CE) options were compared i.e. screening via Pap smear; modeling of HPV vaccination (QV and BV) and combined strategy (screening plus vaccination). Scenario based sensitivity analysis using screening population coverage (40-80%) and costs of vaccine (RM 100-200/dose) were calculated. METHODS: This is a cross sectional study from 2006-2009 and respondents were interviewed from six public Gynecology-Oncology hospitals. Methods include experts’ panel discussions to estimate treatment costs by severity and direct interviews with respondents using costing and quality of life questionnaires. RESULTS: 502 cervical cancer patients participated with mean age at 53.3 ± 11.21 years, Malays (44.2%) and married for 27.73 ± 12.12 years. Cost/QALYs for Pap smear at base case is RM 1,214.96/QALYs and RM 1,100.01/QALYs at increased screening coverage. In QV only, cost/QALYs saved in base case are at RM 15,662/QALYs and RM 24,203/QALYs when vaccination price is increased. In BV only; cost/QALYs saved in base case is at RM 1,359,057/QALYs and RM 2,530,017.56/QALYs when vaccination price is increased. In QV combined strategy cost/QALYs at base case is RM 4,937/QALYs; RM 3,395/QALYs at best case and RM 7,992/QALYs at worst case scenario. In BV combined strategy, cost/QALYs at base case is RM 6,624/QALYs; RM 4,033/QALYs at best case and RM 10,543/QALYs at worst case scenario. Incremental cost-effectiveness ratio (ICER) showed that screening at 70% coverage or higher is highly cost effective at RM 946.74 per QALYs saved and this is followed by best case combined strategy with QV  at RM 13,000 per QALYs saved.  CONCLUSIONS: QV is more cost effective than BV. The QV combined strategy is more CE than any method except Pap smear screening at high population coverage.