High-entropy alloys (HEAs) exhibit complex phase formation behavior, challenging conventional predictive methods. This study presents a machine learning (ML) framework for phase prediction in HEAs, using a curated dataset of 648 experimentally characterized compositions and features derived from thermodynamic and electronic descriptors. Three classifiers—random forest, gradient boosting, and CatBoost—were trained and validated through cross-validation and testing. Gradient boosting achieved the highest accuracy, and valence electron concentration (VEC), atomic size mismatch (δ), and enthalpy of mixing (ΔHmix) were identified as the most influential features. The model predictions were experimentally verified using a non-equiatomic Al30Cu17.5Fe17.5Cr17.5Mn17.5 alloy and the equiatomic Cantor alloy (CoCrFeMnNi), both of which showed strong agreement with predicted phase structures. The results demonstrate that combining physically informed feature engineering with ML enables accurate and generalizable phase prediction, supporting accelerated HEA design.