We examined the anxiety of medical students when they conduct their first gynecological examination. The students (226) from two universities completed anonymous questionnaires providing measures of state and trait anxiety and anxiety and confidence feelings, before and after conducting their first bimanual and speculum examination. This took place during a structured, self-directed learning session and involved examination of a professional patient. Students state anxiety was significantly elevated immediately before and fell to below baseline levels after the examination (p < 0.001). Students’ reported feelings of increased confidence during the examination (p < 0.001). Students who had personally had a Pap smear test were most anxious before (p < 0.003) but during the examination, students who had experienced a gynecological exam felt less anxious (p < 0.002). The students experiencing the greatest decreases (before to after) in state anxiety were those who had never experienced sexual intercourse (p < 0.005). Most students (96%), particularly those who were more anxious during the examination (p < 0.001) and who experienced a greater decrease in anxiety from before to after the examination (p < 0.008) would recommend this method of learning to other students. In summary, medical students are anxious when they conduct their first gynecological examination, appear to be influenced by their personal experiences and appreciate methods of learning that reduce their anxiety.