We integrate a deep machine learning (ML) method with first-principles calculations to efficiently search for the energetically favorable ternary compounds. Using La-Si-P as a prototype system, we demonstrate that ML-guided first-principles calculations can efficiently explore crystal structures and their relative energetic stabilities, thus greatly accelerate the pace of material discovery. A number of new La-Si-P ternary compounds with formation energies less than 30 meV/atom above the known ternary convex hull are discovered. Among them, the formation energies of La5SiP3 and La2SiP phases are only 2 and 10 meV/atom, respectively, above the convex hull. These two compounds are dynamically stable with no imaginary phonon modes. Moreover, by replacing Si with heavier-group 14 elements in the eight lowest-energy La-Si-P structures from our ML-guided predictions, a number of low-energy La-X-P phases (X = Ge, Sn, Pb) are predicted.