What equation (/solution) predicts the existence of black holes? Where does our theoretical prediction of the existence of black holes come from? If it is (as I am guessing) from the Einstein Field Equations, which solution predicts it and why? 
 A: 
Where does our theoretical prediction of the existence of black holes come from?

It comes from the singularity theorems of Hawking and Penrose. Before then, people were aware of solutions to Einstein's Field Equations that had singularities but they required absolutely perfect symmetries, such as perfect radial symmetry for Schwarzschild, or perfect axial symmetry for Kerr.
Lifshitz and Khalatnikov (1963) should have an account of the work people did trying to show that perfect and unachievable exactness would be required to make a black hole. And at that point people really thought that singularities might be impossible to actually make. They thought if you you tried to make one then the absolutely slightest mistake could instead make one not form. Which means there wouldn't really be any in nature, just some mathematical solutions that never apply to the real world
Then everything changed in 1965 when Penrose showed (roughly) that if you pushed something inside the event horizon (roughly) it would have to form a singularity (with some other assumptions). This is in contrast to say, Newtonian physics where small enough particles can swirl around the common center of mass and never collide.
There is a big caveat in that you have to assume it gets compressed enough and then the singularity forms. Observers on the outside don't see it get compressed enough, so there is still no evidence of a singularity. Hawking then made some singularity theorems too, for instance which implied that if you look at earlier and earlier times the big bang was itself a singularity. And then by the 1980's Hawking said that really he thinks quantum effects come up before a singularity is formed so we don't really know.
But the singularity theorems starting in the mid 1960's are when we first thought that singularities were a real world prediction of General Relativity. I.e. that General Relativity predicts that singularities would exist in the real world if General Relativity is true of the real world at all length and time scales. But the caveat still applies. And the caveat has been updated to the Cosmic Censorship Conjecture, where people hypothesize that we will never have evidence of a singularity formation because we will always avoid seeing too much matter or energy or stress or pressure or momentum get trapped by a surface of too small a surface area.
A: From a historical perspective black holes weren't predicted. In 1916 Karl Schwarzschild found a solution to Einstein's equations for a spherically symmetric mass. It was only subsequently realised that the Schwarzschild metric is a vacuum solution with an event horizon and a curvature singularity at its centre, and that the metric describes a static uncharged black hole. It took until the end of the fifties (over 40 years!) before the black hole nature of Schwarzschild's solution was fully understood.
Following Schwarzschild's solution, three more solutions were found describing charged, rotating and charged-rotating black holes. These are the Reisner-Nordström, Kerr and Kerr-Newman metrics. These four metrics are the only known black hole solutions.
