High participation in cervical cancer screening is essential for an effective screening program. In this population-based study, we investigated associations between general health, lifestyle and sexual behavior, and non-participation in cervical cancer screening in Denmark. During 2011–2012, a random sample of women aged 18–45 years from the general female population were invited to participate in a survey regarding health, lifestyle and sexual habits. Altogether 18,631 women responded (response rate: 75.1%), of whom 14,271 women aged 23–45 years were included in this analysis. Information on screening participation within four years after response, and data on sociodemographic characteristics, was obtained from nationwide registers. Logistic regression was used to calculate odds ratios (ORs) for non-participation, crude and adjusted for sociodemographic characteristics. Overall, 13.9% of the women were not screened during follow-up. The odds of non-participation was increased in women who were overweight (OR_adj. = 1.20; 95% CI, 1.06–1.35), obese (OR_adj. = 1.46; 95% CI, 1.27–1.67), perceived themselves as much too fat (OR_adj. = 1.50; 95% CI, 1.29–1.74), had poor self-perceived health (OR_adj. = 1.22; 95% CI, 1.03–1.45) or smoked daily (OR_adj. = 1.81; 95% CI, 1.61–2.03). Conversely, women with previous genital warts or other sexually transmitted infections, and young women with ≥10 lifetime sexual partners or ≥2 new recent partners, had decreased odds of non-participation. In conclusion, obesity, poor self-perceived health and daily smoking were associated with lower participation in cervical cancer screening. Interventions targeting these groups are needed.