Early warning prediction of traumatic hemorrhagic shock (THS) can greatly reduce patient mortality and morbidity. We aimed to develop and validate models with different stepped feature sets to predict THS in advance. From the PLA General Hospital Emergency Rescue Database and Medical Information Mart for Intensive Care III, we identified 604 and 1,614 patients, respectively. Two popular machine learning algorithms (i.e., extreme gradient boosting [XGBoost] and logistic regression) were applied. The area under the receiver operating characteristic curve (AUROC) was used to evaluate the performance of the models. By analyzing the feature importance based on XGBoost, we found that features in vital signs (VS), routine blood (RB), and blood gas analysis (BG) were the most relevant to THS (0.292, 0.249, and 0.225, respectively). Thus, the stepped relationships existing in them were revealed. Furthermore, the three stepped feature sets (i.e., VS, VS + RB, and VS + RB + sBG) were passed to the two machine learning algorithms to predict THS in the subsequent T hours (where T = 3, 2, 1, or 0.5), respectively. Results showed that the XGBoost model performance was significantly better than the logistic regression. The model using vital signs alone achieved good performance at the half-hour time window (AUROC = 0.935), and the performance was increased when laboratory results were added, especially when the time window was 1 h (AUROC = 0.950 and 0.968, respectively). These good-performing interpretable models demonstrated acceptable generalization ability in external validation, which could flexibly and rollingly predict THS T hours (where T = 0.5, 1) prior to clinical recognition. A prospective study is necessary to determine the clinical utility of the proposed THS prediction models.