This work investigates the failure envelope of a rectangular skirt foundation in non-homogeneous clays based on the new novel soft-computing approach that combines FELA simulation and tree machine learning models, including decision tree (DT), random forest (RF), and gradient boosting (GB) models. The impacts of embedment depth (D/B), shape ratio (L/B), and soil heterogeneity (κ) that affect the failure envelope of the rectangular skirt foundation under combined loading conditions, including the vertical load (V), horizontal load (H), and moment (M), are investigated. Furthermore, decision trees, random forests, and gradient boosting are selected to consider the relationships between the investigated parameters and the failure envelope capacity (V/Asu, H/Asu, M/ALsu). To facilitate practical application, the numerical findings are given in the form of design charts and tables. The efficiency of the tree models is determined through regression parameters (i.e., R2, RMSE, MSE, and MAE) combined with a Taylor chart. As a result, the decision tree model is suggested as the best model (R2 = 0.999) for predicting the failure envelope of rectangular skirt foundations. Additionally, the failure mechanism of rectangular skirt footing in heterogeneous clay under combined loading (V, H, M) has been examined, enhancing the design of engineers in practice.