Background The study evaluated acceptability, invitation letters and the test kit for a trial of human papillomavirus (HPV) self-sampling among never- and under-screened women in Australia. Methods: Victorian women, 30–69 years, who had never had a Pap test or were overdue for one, participated. Four focus groups including eight to nine participants segmented by age (30–49 and 50–69 years) and screening history (never- and under-screened) were conducted in August 2013. Discussions were recorded and transcribed verbatim and data analysed using thematic content analysis. Results: The response to the concept of HPV self-sampling was positive. Decision-making was largely influenced by the content of a pre-invitation letter. Appealing features of self-sampling were cost (free), convenience (home-based) and anticipated less discomfort (with a swab) than a Pap test. Small kits that fit in mailboxes were preferred over post office parcel collection. The perceived barriers include concerns about test accuracy and lack of confidence that a home-based test would give the same results as a physician administered test. Women wanted information on the timing of receipt of the results and information about the organisation providing the test. Conclusion: HPV self-sampling is a possible alternative for Australian women who are reluctant to have a Pap test and may increase the likelihood of participation in cervical cancer screening if women’s concerns about it can be addressed. The findings of this study are relevant for researchers, policymakers and practitioners implementing self-sampling for under-screened women as part of cervical screening programs.