String theory is a quantum theory of gravity, and has had several amazing successes in describing black holes. After discussing some paradoxes related to the physics of black holes, I will explain how to construct black holes in string theory, and how to count their entropy. I will then describe a new paradigm in the study of black holes that recent research appears to support: a black hole solution gives only a thermodynamic description of the physics, and the "microscopical" statistical description of the physics is given by a very large number of microstate geometries, that look the same as a black hole from far away, but do not have a horizon.