Objective: Mental health problems (MHP) are a relatively common consequence of deployment to war zones. Early identification of those at risk of post-deployment MHP would improve prevention efforts. However, screening instruments based on linear models have not been successful. Machine learning (ML) has shown promise for providing the methodological frame for better prognostic models. Methods: The study population was all Danish military personnel deployed for the first time between January 1, 1992 and December 31, 2013. From extensive registry data, 21 pre- or at-deployment predictors comprising early adversity, social, clinical and demographic variables were used to predict psychiatric contacts (psychiatric diagnosis and/or use of psychotropic medicine) occurring within 6.5 years after homecoming. Four supervised ML methods (penalized logistic regression, random forests, support vector machines and gradient boosting machines) were compared in ability to classify those with high risk of post-deployment MHP and those without. Results: Of 27594 subjects, 2175 (8%) had a psychiatric contact. All four ML methods applied had performances well above chance (Area under the Receiver-operating Curve 0.62-0.68). Positive predictive value for the best model was 0.16. A range of pre-deployment factors were found to be predictive of post-deployment psychiatric contacts. Conclusions: ML methods can be useful in early identification of soldiers with high risk of MPH in the years following their first deployment. However, performances were modest and positive predictive values were low, limiting the applicability of the models for pre-deployment screening. Future studies should include neurobiological data and deployment experiences to increase accuracy of the models.