Following the latest update of cervical cancer screening guidelines in 2012, we estimate the prevalence of guideline adherent cervical cancer screening and examine its associated factors among a nationally representative sample of US women aged 21–65 years. Our study was based on cross-sectional data from Cycles 3 (2013) and 4 (2014) of the Health Information National Trends Survey. The final analytic sample consisted of 2822 women. Guideline adherent cervical cancer screening was defined as having a Pap test within the last 3 years. Correlates of guideline adherent cervical cancer screening included socio-demographic and health-related characteristics and HPV/cervical cancer-related beliefs and knowledge items. Multivariable logistic regression analyses were used to estimate prevalence of guideline adherent screening. An estimated 81.3% of women aged 21–65 years reported being screened for cervical cancer within the last 3 years. Controlling for sociodemographic and health-related characteristics and survey year, women aged 46–65 years were less likely to be guideline adherent than those aged 21–30 years (aPR = 0.89; 95% CI 0.82–0.97). The adjusted prevalence of adherence was significantly higher among married/partnered than among not married women (aPR = 1.13; 95% CI 1.05–1.22), and those with one to three medical visits (aPR = 1.30; 95% CI 1.14–1.48), and four or more visits in the past year (aPR = 1.26; 95% CI 1.09–1.45) compared to those with no medical visits. Differences in unadjusted prevalence of guideline adherent screening depending on women’s beliefs and knowledge about HPV and cervical cancer were not significant in adjusted analyses. Lack of interaction with a healthcare provider, being not married/partnered and increasing age continue to be risk factors of foregoing guideline adherent cervical cancer screening.