OBJECTIVE Individuals with mental health problems are at elevated risk for eating disorders. Veterans serving in support of the conflicts in Afghanistan and Iraq (OEF/OIF) have a high prevalence of deployment-related mental health problems, but little is known about their risk for eating disorders. Our aim was to determine rates of eating disorder diagnoses among OEF/OIF veterans with mental health problems, particularly among those with comorbid mental health problems. METHODS This retrospective, cross-sectional analysis of nationwide VA healthcare facilities used descriptive statistics and regression analyses to determine eating disorder rates in OEF/OIF veterans who were new users of VA healthcare from October 7, 2001 to December 31, 2010 (N = 593,739). RESULTS Although the prevalence of eating disorder diagnoses was 0.007% (n = 465) in women and <0.001% (n = 192) in men, veterans diagnosed with mental health problems were significantly more likely to have an eating disorder than those without mental health diagnoses. Eating disorders were significantly more common in women with depression, posttraumatic stress disorder, and alcohol and/or drug use disorders than in women veterans without these mental health disorders. Among men, the associations between eating disorder diagnoses and comorbid mental health diagnoses closely paralleled those observed in women. CONCLUSIONS Rates of eating disorders are significantly higher among returning veterans with comorbid mental health problems compared with those without mental health diagnoses. Further research should examine methods to improve detection and treatment of eating disorders in this population.