Aboriginal and Torres Strait Islander (collectively, Indigenous Australian) women experience a higher burden of cervical cancer than other women. The National Cervical Screening Program (NCSP) is failing to meet the needs of Indigenous Australian women, resulting in many women not regularly participating in cervical screening. However, one third of Indigenous Australian women do participate in cervical screening. The reasons that some women in this population commence and continue to screen remain unheard but could provide insights to support women who currently do not participate. We aimed to describe Indigenous Australian women’s experiences and views of participation in cervical screening by yarning (a culturally-appropriate interview technique) with 50 Indigenous Australian women aged 25–70 years who had completed cervical screening in the past five years, recruited via Primary Health Care Centres (PHCCs) from three jurisdictions. Aboriginal or Torres Strait Islander women researchers conducted the interviews. Thematic analysis identified six themes: screening as a means of staying strong and in control; overcoming fears, shame, and negative experiences of screening; needing to talk openly about screening; the value of trusting relationships with screening providers; logistical barriers; and overcoming privacy concerns for women employed at PHCCs. Despite describing screening as shameful, invasive, and uncomfortable, women perceived it as a way of staying healthy and exerting control over their health. This ultimately supported their participation and a sense of empowerment. Women valued open discussion about screening and strong relationships with health providers. We identified logistical barriers and specific barriers faced by women employed at PHCCs. This study is strengthened by a research approach that centred Indigenous Australian women’s voices. Understanding the experiences of Indigenous Australian women who participate in screening will help screening providers support women to start and continue to screen regularly. Recommendations for practice are provided.