Background Problem drinking that predates enlistment into military service may contribute to the overall burden of alcohol misuse in the Armed Forces; however, evidence bearing on this issue is limited. This study examines prevalence and correlates of alcohol misuse among new U.S. Army soldiers. Methods Cross-sectional survey data were collected from soldiers reporting for basic combat training. The survey retrospectively assessed lifetime alcohol consumption and substance abuse/dependence, enabling estimation of the prevalence of lifetime binge drinking and heavy drinking in a sample of 30,583 soldiers and of probable alcohol use disorder (AUD) among 26,754 soldiers with no/minimal lifetime use of other drugs. Co-occurrence of mental disorders and other adverse outcomes with binge drinking, heavy drinking, and AUD was examined. Discrete-time survival analysis, with person-year the unit of analysis and a logistic link function, was used to estimate associations of AUD with subsequent onset of mental disorders and vice versa. Results Weighted prevalence of lifetime binge drinking was 27.2% (SE = 0.4) among males and 18.9% (SE = 0.7) among females; respective estimates for heavy drinking were 13.9% (SE = 0.3) and 9.4% (SE = 0.4). Among soldiers with no/minimal drug use, 9.5% (SE = 0.2) of males and 7.2% (SE = 0.5) of females had lifetime AUD. Relative to no alcohol misuse, binge drinking, heavy drinking, and AUD were associated with increased odds of all mental disorders and other adverse outcomes under consideration (adjusted odds ratios [AORs] = 1.5 to 4.6; ps < 0.001). Prior mental disorders and suicidal ideation were associated with onset of AUD (AORs = 2.3 to 2.8; ps < 0.001), and prior AUD was associated with onset of mental disorders and suicidal ideation (AORs = 2.0 to 3.2, ps < 0.005). Conclusions Strong bidirectional associations between alcohol misuse and mental disorders were observed in a cohort of soldiers beginning Army service. Conjoint recognition of alcohol misuse and mental disorders upon enlistment may provide opportunities for risk mitigation early in a soldier's career.