There is limited access to cervical cancer screening facilities at health centers in the districts of Uganda. The objective of the study was to perform Cost-Benefit Analysis (CBA) of screening women for cervical cancer at health centers in the districts of Uganda using Papanicolaou method. Pilot screening services were established at selected health centers in selected districts of Uganda using Papanicolaou method. CBA was performed under two scenarios. Scenario 1 was when there are no screening services at district health centers and all women were referred to Mulago hospital for screening. Scenario 2 was when there was screening services at health centers and only processed Papanicolaou smears which were sent to Pathology department for interpretation. The cost of screening for cervical cancer would be high both in scenario 1 and 2 in the first year. The screening costs would drastically reduce in scenario 2 in the second and subsequent years. However, screening women in eastern Uganda would be associated with high savings as compared with western region. Screening women at health centers in northern and central regions would be insensitive and associated with loses both in year one and subsequent years because of low number of women who would be screened. Papanicolaou screening was sensitive to the number of women screened and the distance from the screening center. Screening women at districts health centres distant from Mulago hospital would be the most cost effective intervention if many women are screened. Referring women to Mulago from health centers near Mulago hospital would be the cheapest option.