Introduction: A number of studies have found an association between sickle cell trait (SCT) and exertional heat illnesses (EHIs) including heat stroke, a potentially fatal condition. The strength of this association varied across studies, limiting the ability to quantify potential benefits of SCT-screening policies for competitive athletics and military service members. We determined the relative rate and attributable risk of developing EHI associated with being SCT positive and the EHI health care utilization. Methods: We conducted a retrospective cohort study among U. S. enlisted, active duty service members during 1992-2012 from the Department of Defense Military Healthcare System databases. All 15,081 SCT-positive individuals and a sample of 60,320 from those considered SCT negative were followed through 2013 for EHI outcomes ranging from mild heat illness to heat stroke. Results: The adjusted hazard ratio for EHI in SCT-positive compared with SCT-negative individuals was 1.24 (95% confidence interval 1.06, 1.45). Risk factors for EHI included age over 30 yr at enlistment, female gender, Marine Corps, combat occupations, and enlistment between April and June. An estimated 216 Department of Defense enlistees (95% confidence interval: 147, 370) would need to be screened to identify and potentially prevent one case of EHI. The attributable risk of EHI due to SCT was 33% (95% confidence interval 19, 45%). Conclusion: Our findings suggest that SCT screening will identify approximately a third of SCT individuals at risk for EHI, but does not provide definitive evidence for universal compared with selective (e.g., occupational based) in military enlistees. A cost-effectiveness analysis is needed for policy makers to assess the overall value of universal SCT screening to prevent morbidity and mortality in both the military and the collegiate athletic populations.