Medium-entropy alloys (MEAs) are a class of alloys composed of a small number (typically three to four) of principal elements in near-equiatomic ratios. They exhibit a balance between the structural stability of high-entropy alloys (HEAs) and the controllability of conventional alloys, demonstrating excellent mechanical properties, thermal stability, and corrosion resistance. However, the design of MEAs still relies primarily on empirical and trial-and-error methods, making it challenging to accurately predict their phase structures and properties. This study proposes a machine learning-based regression and classification framework to predict the phase structures of quaternary equiatomic MEAs. A dataset of 731 alloy samples was compiled from the literature and categorized into three phase structures: face-centered cubic (FCC, 158 samples), body-centered cubic (BCC, 151 samples), and mixed or amorphous-like structures (none, 422 samples). Seven key features including valence electron concentration (VEC), mixing enthalpy (ΔH mix), atomic size difference (δ), electronegativity difference (Δχ), and maximum, minimum, and average densities—were selected to establish a mathematical model describing the relationship between alloy composition and structure. Three machine learning algorithms—random forest (RFC), support vector machine (SVC), and extreme gradient boosting (XGBoost)—were employed, with hyperparameter optimization conducted using grid search and ten-fold cross-validation. The results indicate that XGBoost is the best-performing model, achieving an accuracy of 0.939 on the test set, outperforming RFC (0.932) and SVC (0.721). Additionally, XGBoost demonstrated superior F1-scores, with 0.947 for the FCC class, 0.923 for BCC, and 0.943 for none, surpassing the other models. These findings confirm that XGBoost effectively identifies key factors influencing phase stability and serves as a reliable predictive tool for the composition optimization of MEAs.