A high number of military veterans seek professional help at primary healthcare centers for mental health problems. The main aim of this study was to map veterans’ perception of the quality of the care they received when seeking such help after their last tour of duty. A secondary aim was to explore personality and mission-related characteristics of veterans who seek professional help for mental health problems after missions. Questionnaire responses were obtained from 2512 Swedish veterans (43.4% response rate). Among the responders, 210 individuals had sought help for mental health problems at primary healthcare centers. Their perception of the quality of the healthcare was measured using the Quality from the Patient’s Perspective (QPP) questionnaire, which is derived from a theoretical model. Comparisons between the military help seekers and an age and gender matched group of civilian outpatients showed that the military group perceived the information they had received, and the commitment, empathy and respect shown by the physicians, considerably more negatively than the civilian patients. Comparisons between the help-seeking veterans and those who had not sought help, showed that the help seekers were younger and scored significantly lower on emotional stability and higher on conscientiousness. In addition, they perceived the leadership of their immediate commander during the last tour of duty more negatively and they reported fewer daily uplifts and more daily hassles during the tour. It was concluded that a more extensive collaboration between the armed forces and the healthcare system is strongly recommended and that it is necessary to provide education to healthcare providers.