Background: Data on the knowledge of the general population of Uzbekistan regarding human papillomavirus (HPV) infection and cervical cancer screening practices are limited. This study aimed to assess the association between the knowledge and practice of cervical cancer screening among women in Uzbekistan. Methods: A baseline survey was conducted with 445 women aged 20–59 years who visited one of the three health centres of Tashkent, Uzbekistan, in December 2020. A questionnaire on the knowledge of HPV infection and cervical cancer screening practices was administered. The knowledge score, defined as the sum of the number of correct answers to the knowledge questions and the prevalence of cervical cancer screening practices, was analysed. The adjusted relative risk (RR) and low knowledge score (median) of (1) never screened and (2) not screened within 2 years for each demographic characteristic were calculated. Results: The median knowledge score was 10. Women who had been screened for cervical cancer accounted for 63.1% of the patients. Among them, 64.8% reported that their last cervical cancer screening test was within 2 years. A history of sexually transmitted diseases was associated with a lower risk of never being screened (adjusted RR = 0.43, 95% confidence interval [CI] 0.24, 0.78) and no screening within 2 years (0.54, 95% CI 0.30, 0.99). No university graduation was associated with a higher risk of not screening within 2 years (1.57, 95% CI 1.00, 2.47). Association between knowledge of HPV status and screening practices was not observed. Conclusions: Adequate knowledge of HPV and cervical cancer prevention may be insufficient for cervical cancer screening practices. This study provides context for the development of effective cervical cancer prevention strategies.