Local delivery of chemotherapeutics in the cervicovaginal tract using nanoparticles may reduce adverse side effects associated with systemic chemotherapy, while improving outcomes for early-stage cervical cancer. It is hypothesized here that drug-loaded nanoparticles that rapidly penetrate cervicovaginal mucus (CVM) lining the female reproductive tract will more effectively deliver their payload to underlying diseased tissues in a uniform and sustained manner compared with nanoparticles that do not efficiently penetrate CVM. Paclitaxel-loaded nanoparticles are developed, composed entirely of polymers used in FDA-approved products, which rapidly penetrate human CVM and provide sustained drug release with minimal burst effect. A mouse model is further employed with aggressive cervical tumors established in the cervicovaginal tract to compare paclitaxel-loaded poly(lactic-co-glycolic acid) (PLGA) nanoparticles (conventional particles, or CP) and similar particles coated with Pluronic F127 (mucus-penetrating particles, or MPP). CP are mucoadhesive and, thus, aggregated in mucus, while MPP achieve more uniform distribution and close proximity to cervical tumors. Paclitaxel-MPP suppress tumor growth more effectively and prolong median survival of mice compared with unencapsulated paclitaxel or paclitaxel-CP. Histopathological studies demonstrate minimal toxicity to the cervicovaginal epithelia, suggesting paclitaxel-MPP may be safe for intravaginal use. These results demonstrate the in vivo advantages of polymer-based MPP for treatment of tumors localized to a mucosal surface.