Background In Germany, immunization against human papillomaviruses (HPV) is free of charge for all females aged 12 to 17 years. Since HPV infection rates rise soon after first intercourse, immunization against HPV should be completed before sexual debut. Knowledge of country-specific data on age at first intercourse and related risk factors is important to optimize prevention of HPV and other sexually transmitted infections. Therefore, the primary aim of this study was to describe sexual behavior in young women in Germany. Secondary aims were to identify factors that are (i) associated with younger age at first intercourse and (ii) with HPV vaccine uptake. Methods Between 2010 and 2012, we conducted a cross-sectional study among randomly selected women aged 20 to 25 years in Germany. We used a structured, self-administered questionnaire to collect sociodemographic data, information on sexual habits such as age at first intercourse, and information on HPV vaccine uptake. We used univariate and multivariate logistic regression analyses to identify factors associated with younger age at first intercourse and with HPV vaccine uptake. Results A total of 823 women (response rate: 14.2%) participated, 785 (95.4%) of which reported having had intercourse already. 70% of these women experienced first intercourse before the age of 18 years. However, less than 5% were younger than 14 years at sexual debut. Younger age at first intercourse was independently associated with a higher number of sexual partners, smoking, and past pregnancies. HPV vaccine uptake was associated with higher education, whereas smoking and a migrant background reduced the chance of being vaccinated. Conclusion In Germany, only a small proportion of women experienced first intercourse before the age of 14 years. Younger age at first intercourse was associated with behavior that might increase the risk of HPV infections or other sexually transmitted infections. Therefore, to optimize the HPV vaccination strategy, HPV vaccination series should be completed before the age of 14 years in Germany.