Objective Exertional heat stroke (EHS), characterised by a high core body temperature (Tcr) and central nervous system (CNS) dysfunction, is a concern for athletes, workers and military personnel who must train and perform in hot environments. The objective of this study was to determine whether algorithms that estimate Tcr from heart rate and gait instability from a trunk-worn sensor system can forward predict EHS onset. Methods Heart rate and three-axis accelerometry data were collected from chest-worn sensors from 1806 US military personnel participating in timed 4/5-mile runs, and loaded marches of 7 and 12 miles; in total, 3422 high EHS-risk training datasets were available for analysis. Six soldiers were diagnosed with heat stroke and all had rectal temperatures of >41°C when first measured and were exhibiting CNS dysfunction. Estimated core temperature (ECTemp) was computed from sequential measures of heart rate. Gait instability was computed from three-axis accelerometry using features of pattern dispersion and autocorrelation. Results The six soldiers who experienced heat stroke were among the hottest compared with the other soldiers in the respective training events with ECTemps ranging from 39.2°C to 40.8°C. Combining ECTemp and gait instability measures successfully identified all six EHS casualties at least 3.5 min in advance of collapse while falsely identifying 6.1% (209 total false positives) examples where exertional heat illness symptoms were neither observed nor reported. No false-negative cases were noted. Conclusion The combination of two algorithms that estimate Tcr and ataxic gate appears promising for real-time alerting of impending EHS.