Phase prediction enables the rational design of high entropy alloys from a practically infinite unexplored space. However, the reliable and efficient prediction of phases remains a challenge. We establish an accurate, physically interpretable and easily accessible descriptor based two-dimensional (2D) map for phase prediction of high entropy alloys. The descriptors are constructed with an interpretable machine learning algorithm by combining empirical descriptors using arithmetic operations. We demonstrate that these descriptors lead to much greater accuracy for solid solutions or intermetallics, dual phases (FCC, face-centered-cubic and BCC, body-centered-cubic) and single phases (FCC or BCC) compared to commonly used empirical descriptors. The prediction accuracies for crystal or amorphous, and BCC or FCC reach ∼95%. Descriptors with differing length scales that have not been considered for phase prediction are proposed, providing opportunities to clarify the physics underlying the formation and stability of different phases. We validate the approach in three typical high entropy alloys systems via experimental synthesis and characterization, as well as in a group of 14 alloys belonging to 8 new systems outside the initial data. We show that the descriptors can accurately predict the phase structures.