Background: Little is known about gender differences in mental health, related help-seeking behavior and social support in UK military personnel. Methods: 1714 UK military serving personnel and ex-service veterans were randomly selected if, in a cohort study, they endorsed experiencing a subjective stress, emotional, alcohol or mental health problem in the previous three years. Following exclusions, the final sample size was 1448 (participation rate 84.5%; women n = 219). Structured telephone interviews assessed anxiety, depression, PTSD symptoms, alcohol use, help-seeking and social support occurring both currently and in the past three years. Outcomes were assessed using weighted unadjusted and adjusted logistic regression analyses. Results: Mental health problems assessed at interview were broadly similar for men and women; for both genders, levels of social support were high. One-fifth of respondents screened positive for probable mental disorder or alcohol misuse; although rates of mental disorder symptoms did not differ by gender, women were significantly less likely than men to report alcohol misuse. Women were significantly more likely to have sought help from formal medical sources but significantly less likely to access informal support such as friends, family or unit welfare sources; reasons for seeking formal medical support were similar for men and women except for problem recognition and acting on advice from others, which were both significantly more common among women. Conclusion: For military personnel with a history of mental ill-health, women should make greater use of informal support networks while for men, engagement with formal medical help sources should be encouraged.