<p>Fatigue strength stands as a pivotal property for any structural material, constituting approximately 90% of all structural material failures. Despite its significance, a comprehensive exploration of fatigue failures through a data-driven approach has been hindered by the limited availability of fatigue strength data. Previous studies on fatigue strength prediction based on alloying composition and heat-treatment processes focused on limited categories of steel from the dataset presented by the National Institute of Material Science (NIMS). This research broadens the scope of previous studies by employing a large dataset of a wide range of steel and comprising 3612 data points. Seven algorithms were trained, and the best-performing model achieved an impressive accuracy with an <i>R</i>² score of 0.96. The correlations between fatigue strength and the rest of the features were scrutinized with correlation heatmap, sequential feature selector, partial dependence plots, and Shapley value plots to reveal the most important factors for engineering fatigue strengths in steels. Chromium, nickel, and carbon were found to be the most important additives, while the overall level of alloying was also found to be an important contributor to fatigue strength of steels. This study specifically focused on process–composition–property relationships, as composition and process are the key variables that can be tuned to engineer novel alloys.</p>