Women born between 1994 and 1999 achieved high vaccination rates for human papillomavirus (HPV); they are now reaching the age of cervical cancer screening programs in Japan. In this study, we aimed to investigate the health awareness of HPV-vaccinated and unvaccinated women and to create tailored leaflets recommending cervical cancer screening for each. Surveys on the cancer screening rates for HPV-vaccinated and unvaccinated women aged 20 and 21 have demonstrated that the rate was significantly higher (p < 0.01) in vaccinated (6.2%) than in unvaccinated women (3.1%). Next, interviews and Internet questionnaires clarified that there was a trend that vaccinated women have a better health consciousness than the unvaccinated ones, and that in unvaccinated women, their willingness to receive cervical cancer screening was significantly enhanced by the fear of developing cancer. Finally, in a prospective study, the increase in the screening rate for both vaccinated and unvaccinated groups after they read tailored leaflets, from 6.4% to 7.4% and from 3.9% to 5.1%, respectively, was not statistically significant compared to the groups provided with a standard reminder letter. Cervical cancer control measures might be enhanced by recommending cervical cancer screening in ways better tailored to HPV vaccination status.