Black holes were first predicted by astrophysics, then observed. Was the existence of galaxies first predicted by astrophysics, or first observed by astronomers?
The idea of the existence of galaxies is certainly not new, and quite a bit older than the field of modern astrophysics.
In 1750, Thomas Wright, an English astronomer correctly speculated that the Milky Way was a flattened disk of stars and that some of the nebulae astronomers viewed in their telescopes were separate "Milky Ways".
In 1755 Immanuel Kant introduced the term "island universe" for these distant nebulae.
In 1912, Vesto Slipher made spectrographic studies of the brightest spiral nebulae to determine if they were made of chemicals found in a planetary system. He discovered they had high red shifts, indicating they were moving away at a rate higher than the milky way's escape velocity.
The matter was conclusively settled in 1922 when Ernst Öpik gave a distance determination which supported the theory that the Andromeda Nebula is an extra-galactic object.
Some galaxies are observable with the naked eye, so people have "observed" them (though not always knowing their true nature) as long as there has been humans. As mentioned in @ghoppe's answer, the idea that they were actually large formations of stars like the Milky Way formed gradually through the age of Enlightenment, which I guess are the first "models", albeit non-quantitative, of galaxies. So they had been observed for millennia before any scientific explanation for them came up.
That is certainly not the case with Black Holes; they are extremely hard to observe, so it makes sense that people only started looking for them once they suspected from physical theory that they had to be out there.