Background: With the growing proportion of women in the armed forces, insights into their mental health have become increasingly important. The aim of this study was to compare the mental health of young women and men who were deemed eligible for military training at draft board examination. Methods: In this nationwide study, data from draft board examinations at five different sites in Denmark was collected. The assessments included a performance-based test of fluid intelligence and a questionnaire on mental health problems. Results: The sample comprised 103 women and 1273 men who were deemed eligible for the military. The women had significantly fewer mental health problems compared to the men and this result remained when age and intelligence was adjusted for. No difference was found with regard to intelligence. The association between intelligence and mental health was moderated by gender. This reflected that the women with higher intelligence had more mental health problems while the opposite pattern emerged for the men. Conclusions: The findings indicate that women potentially have better mental health than men at entrance to military training. Further research needs to clarify the causes of these gender differences and whether they change over the course of military service.