Background: Cervical cancer screening is a critical health service that is often unavailable to women in under-resourced settings. In order to expand access to this and other reproductive and primary health care services, a South African non-governmental organization established a van-based mobile clinic in two rural districts in South Africa. To inform policy and budgeting, we conducted a cost evaluation of this service delivery model. Methods: The evaluation was retrospective (October 2012–September 2013 for one district and April–September 2013 for the second district) and conducted from a provider cost perspective. Services evaluated included cervical cancer screening, HIV counselling and testing, syndromic management of sexually transmitted infections (STIs), breast exams, provision of condoms, contraceptives, and general health education. Fixed costs, including vehicle purchase and conversion, equipment, operating costs and mobile clinic staffing, were collected from program records and public sector pricing information. The number of women accessing different services was multiplied by ingredients-based variable costs, reflecting the consumables required. All costs are reported in 2013 USD. Results: Fixed costs accounted for most of the total annual costs of the mobile clinics (85% and 94% for the two districts); the largest contributor to annual fixed costs was staff salaries. Average costs per patient were driven by the total number of patients seen, at $46.09 and $76.03 for the two districts. Variable costs for Pap smears were higher than for other services provided, and some services, such as breast exams and STI and tuberculosis symptoms screening, had no marginal cost. Conclusions: Staffing costs are the largest component of providing mobile health services to rural communities. Yet, in remote areas where patient volumes do not exceed nursing staff capacity, incorporating multiple services within a cervical cancer screening program is an approach to potentially expand access to health care without added costs.