Background: The incidence of obstructive sleep apnea (OSA) in the military has risen dramatically. OSA is considered “service connected” and compensable by the Veterans Administration. The association between body mass index (BMI) (kg/m2) measured at initial enlistment and development of OSA has yet to be assessed. Methods: Data were obtained from the Defense Medical Surveillance System, the Armed Forces Health Surveillance Center, U.S. Department of Defense, Silver Spring, Maryland (inclusive dates:1993–2012; release date: December 2013). A study population of 550,000 randomly-selected active duty enlisted personnel was followed retrospectively from January 1, 2008, through December 31, 2012, or until diagnosis with OSA, separation from the military, or death occurred. The main exposure of interest was BMI recorded at time of enlistment. Results: Adjusted hazard ratios for enlistment BMI were calculated using BMI of 23 to 23.9 as reference. Exponentially increasing risk for OSA was observed as BMI increased. The heaviest individuals (BMI > 35) were at the highest risk (hazard ratio: 3.93; 95% confidence interval [CI]: 3.35–4.62) for developing OSA. Conclusion: Enlistment BMI’s role in developing OSA may be valuable in designing screening tools and preventive interventions in higher-risk groups, as well as prompt further consideration in the realm of military enlistment policy.