Black holes come in a number of varieties, depending on how they are formed. Conventional black holes form when stars run out of fuel and collapse in on themselves. If the star is massive enough, about three to ten times the mass of our sun, it forms a black hole.
Another type are the supermassive black holes which sit at the center of many galaxies and are many millions of times more massive than our sun. There is plenty of evidence of both these types of black holes.
Then there are primordial black holes, much more mysterious objects that are thought to have formed soon after the Big Bang. The thinking is that random fluctuations in the distribution of mass in the early universe must have created some regions dense enough to form black holes.