Background: Participation in cervical cancer screening remains low in most countries. Our objective was to evaluate the performance, in terms of participation, and the cost-effectiveness of mailing a vaginal self-sampling (VSS) kit to the homes of women who had not undergone screening, for the purpose of testing for high-risk human papillomavirus (HR-HPV). Methods: In March 2012, 6,000 unscreened women aged 30–65 living in Indre-et-Loire (a department covered by an organized cervical cancer screening program) who had not responded to an invitation to undergo a cervical smear (FCU) were randomized into three groups: "No intervention"; "Reminder": sending a letter encouraging a Pap test; and "Self-sampling": sending a self-sampling kit to be returned to the laboratory for HPV testing. Results: participation was higher in the "self-sampling" group than in the "no intervention" (22.5% vs. 9.9%, p<0.0001) and "reminder" (11.7%, p<0.0001) groups. In the "self-sampling" group, 320 women performed a self-sampling; 40 of the 44 women with a positive HR-HPV test underwent the recommended triage FCU (16.0%). The incremental cost-to-outcome ratios per additional woman screened were €77.8 and €63.2 for the "reminder" and "self-sampling" groups, respectively, compared to the "no intervention" group. Conclusion: Sending a self-sampling kit to the home is more effective and cost-effective than a reminder letter for increasing participation in cervical cancer screening among women who have not been screened.