i-MAX phases, or in-plane ordered MAX phases, are a type of transition metal carbides and/or nitrides with in-plane chemical ordering. They have attracted great attention in recent years due to their fascinating magnetic properties as well as the superior electrochemical properties of their 2D counterparts, called i-MXenes. In this work, we explore the vast chemical space of i-MAX phases via a combined method of high-throughput DFT computation and machine learning to discover new thermodynamically stable compounds. Calculations suggest that many Zn-, Sn- and In- containing compounds are thermodynamically stable, therefore further expanding the attainable A-site chemistries. Using calculation results as training data, an XGBoost model with features including both compositional features and the convex hull energies of 211 MAX phases was used to predict the thermodynamic stabilities of the rest of compounds in the exploration space. The predicted stable compounds were further validated using high-throughput DFT calculations. Such a combined method is able to efficiently uncover 56 (more on hull) new thermodynamic stable i-MAX phases, which are recommended for experimental synthesis.