Two-dimensional transition metal dichalcogenides (TMDs) can adopt one of several possible structures, with the most common being the trigonal prismatic and octahedral symmetry phases. Since the structure determines the electronic properties, being able to predict phase-preferences of TMDs from just the knowledge of the constituent atoms is highly desired, but has remained a long-standing problem. In this study, we applied high-throughput quantum mechanical computations with machine learning algorithms to solve this old problem. Our analysis provides insights into determining physiochemical factors that dictate the phase-preference of a TMD, identifying and going beyond the attributes considered by earlier researchers in predicting crystal structures. A knowledge of these underlying physiochemical factors not only helps us to rationalize, but also to accurately predict structural preferences. We show that machine learning algorithms are powerful tools that can be used not only to find new materials with targeted properties, but also to find connections between elemental attributes and the target property/properties that were not previously obvious.