Laves phases AB2 form the most abundant group of intermetallic compounds, consisting of combinations of larger electropositive metals A with smaller metals B. Many practical applications of Laves phases depend on the ability to tune their physical properties through appropriate substitution of either the A or B component. Although simple geometrical and electronic factors have long been thought to control the formation of Laves phases, no single factor alone can make predictions accurately. Several machine learning models have been developed to discover new Laves phases, including variations caused by solid solubility, using elemental properties solely on the basis of chemical composition. These models were trained on a data set comprising about 3700 entries of experimentally known phases AB2 with Laves and non-Laves structures. Among these models, a decision tree algorithm gave very good performance (average recall of 95%, precision of 94%, and accuracy of 96% on the test set) by using only a small set of descriptors, the most important of which relates to the electron density at the boundary of the Wigner-Seitz cell for the B component. This model provides guidance for new experiments by making predictions on >400000 candidates very quickly. A chemically unintuitive candidate Cd(Cu1-xSbx)2 with a limited solid solubility of Sb for Cu was targeted; it was successfully synthesized and confirmed to adopt a cubic MgCu2-type Laves structure.