Background: This study aimed to assess knowledge, attitudes, and practices regarding cervical cancer, cervical cancer screening, and Papanicolaou (Pap) smear testing among Omani women attending primary healthcare centers in Oman, and to establish a correlation with various sociodemographic characteristics. Methods: A multi-center cross-sectional survey was carried out from August 2019 to January 2020 and included 805 women attending 18 primary healthcare centers. A pre-tested questionnaire was utilized to assess the participants’ sociodemographic characteristics, cervical cancer risk factors, knowledge, attitudes, and practices related to cervical cancer, cervical cancer screening, and Pap smear testing. Results: All 805 women participated in the study (response rate: 100%). Overall, 67.5% and 50.9% had heard of cervical cancer and Pap smear testing, respectively; however, only 13.4% and 10.9% demonstrated high levels of knowledge concerning these topics. Knowledge was significantly associated with educational level, type of educational qualification (i.e. if their degree was related to healthcare), monthly income, and employment status (p ≤ 0.05 each). Only 15.7% of the participants had previously undergone Pap smear testing, although 42.7% were willing to undertake such screening in future. No associations were noted between Pap smear practice or willingness and sociodemographic characteristics, family history of cervical cancer or personal history of cervical cancer or related risk factors. Conclusions: Knowledge regarding cervical cancer and Pap smear testing was suboptimal among a cohort of Omani women attending primary healthcare centers in Oman. This may be a factor behind the increased number of cervical cancer cases in Oman; as such, a well-structured awareness and educational program is needed to address this issue.