Both CALPHAD (CALculation of PHAse Diagrams) and machine-learning (ML) approaches were employed to analyze the phase formation in 2,436 experimentally measured high entropy alloy (HEA) compositions consisting of various quinary mixtures of Al, Co, Cr, Cu, Fe, Mn, and Ni. CALPHAD was found to have good capabilities in predicting the BCC/B2 and FCC phase formation for the 1,761 solid-solution-only compositions, excluding HEAs containing an amorphous phase (AM) or/and intermetallic compound (IM). Phase selection rules were examined systematically using several parameters and it revealed that valency electron concentration (VEC) < 6.87 and VEC > 9.16 are the conditions for the formation of single-phase BCC/B2 and FCC, respectively; and CALPHAD could predict this with essentially 100% accuracy. Both CALPHAD predictions and experimental observations show that more BCC/B2 alloys are formed over FCC alloys as the atomic size difference between the elements increases. Four machine learning (ML) algorithms, decision tree (DT), k-nearest neighbor (KNN), support vector machine (SVM), and artificial neural network (ANN), were employed to study the phase selection rules for two different datasets, one consisting of 1,761 solid-solution (SS) HEAs without AM and/or IM phases, and the other set consisting of all the 2,436 HEA compositions. Cross validation (CV) was performed to optimize the ML models and the CV accuracies are found to be 91.4%, 93.1%, 90.2%, 89.1% for DT, KNN, SVM, and ANN respectively in predicting the formation of BCC/B2, BCC/B2 + FCC, and FCC; and 93.6%, 93.3%, 95.5%, 92.7% for DT, KNN, SVM, and ANN respectively in predicting SS, AM, SS + AM, and IM phases. Sixty-six experimental bulk alloys with SS structures are predicted with trained ANN model, and the accuracy reaches 81.8%. VEC is found to be most important parameter in phase prediction for BCC/B2, BCC/B2 + FCC, and FCC phases. Electronegativity difference and FCC-BCC-index (FBI) are the two additional dominating features in determining the formation of SS, AM, SS + AM, and IM. A separation line was found in the VEC-vs-mixing enthalpy plot to predict the formation of single-phase BCC/B2 or FCC with a 96.2% accuracy. These insights will be very valuable for designing HEAs with targeted crystal structures