Women in low- and middle-income countries (LMIC) remain at high risk of developing cervical cancer and have limited access to screening programs. The limits include geographical barriers related to road network characteristics and travel behaviors but these have neither been well studied in LMIC nor have methods to overcome them been incorporated into cervical cancer screening delivery programs. To identify and evaluate spatial barriers to cervical cancer prevention services in Ondo State, Nigeria, we applied a Multi-Mode Enhanced Two-Step Floating Catchment Area model to create a spatial access index for cervical cancer screening services in Ondo City and the surrounding region. The model used inputs that included the distance between service locations and population centers, local population density, quantity of healthcare infrastructures, modes of transportation, and the travel time budgets of clients. Two different travel modes, taxi and mini bus, represented common modes of transit. Geocoded client residential locations were compared to spatial access results to identify patterns of spatial access and estimate where gaps in access existed. Ondo City was estimated to have the highest access in the region, while the largest city, Akure, was estimated to be in only the middle tier of access. While 73.5% of clients of the hospital in Ondo City resided in the two highest access zones, 21.5% of clients were from locations estimated to be in the lowest access catchment, and a further 2.25% resided outside these limits. Some areas that were relatively close to cervical cancer screening centers had lower access values due to poor road network coverage and fewer options for public transportation. Variations in spatial access were revealed based on client residential patterns, travel time differences, distance decay assumptions, and travel mode choices. Assessing access to cervical cancer screening better identifies potentially underserved locations in rural Nigeria that can inform plans for cervical cancer screening including new or improved infrastructure, effective resource allocation, introduction of service options for areas with lower access, and design of public transportation networks.