Most cervical cancers occur in women who do not participate in cervical-cancer screening. We therefore evaluated adherence to screening for clinic-based Pap testing, self-collected sampling for HPV testing, and choice of the 2 among 483 unscreened/underscreened women in Brazil. Three public Basic Health Units (BHU) were each randomly assigned to three arms: (i) Pap testing at the BHU (N = 160), (ii) "Self HPV" (self-collection for HPV testing) (N = 161), and (iii) "Choice" between self-collection and HPV testing and Pap test at the local BHU (N = 162). The theory-based (PEN-3 and Health Belief Model) intervention in all three arms was implemented by trained Community Health Workers (CHW) at participants' home. With the first invitation, 60.0% in the Pap arm, 95.1% [154 of 161 (95.7%) who selected Self HPV and 0 of 1 (0.0%) who selected Pap] in the Choice arm, and 100% in the Self HPV arm completed screening. By the second invitation to choose a method of screening in the Choice arm, 100% completed screening. After three invitations, 75.0% of women in the Pap arm completed screening. Adherence to screening differed by study arm (P < 0.001). In conclusion, Self HPV testing is a promising strategy for unscreened/underscreened women who are recalcitrant or unable to undergo clinic-based cervical screening to complement the screening modality used in the general population. In Brazil, where Pap testing is recommended for routine cervical screening, training CHWs in behavior change strategies and offering Self HPV or Choice could greatly improve screening population coverage by reaching the unscreened/underscreened populations.