Recently, a new framework for solving the hierarchy problem was proposed which does not rely on low energy supersymmetry or technicolor. The fundamental Planck mass is at a TeV and the observed weakness of gravity at long distances is due the existence of new sub-millimeter spatial dimensions. In this letter, we study how the properties of black holes are altered in these theories. Small black holes---with Schwarzschild radii smaller than the size of the new spatial dimensions---are quite different. They are bigger, colder, and longer-lived than a usual $(3+1)$-dimensional black hole of the same mass. Furthermore, they primarily decay into harmless bulk graviton modes rather than standard-model degrees of freedom. We discuss the interplay of our scenario with the holographic principle. Our results also have implications for the bounds on the spectrum of primordial black holes (PBHs) derived from the photo-dissociation of primordial nucleosynthesis products, distortion of the diffuse gamma-ray spectrum, overclosure of the universe, gravitational lensing, as well as the phenomenology of black hole production. For example, the bound on the spectral index of the primordial spectrum of density perturbations is relaxed from 1.25 to 1.45-1.60 depending on the epoch of the PBH formation. In these scenarios PBHs provide interesting dark matter candidates; for 6 extra dimensions MACHO candidates with mass $\sim 0.1M_\odot$ can arise. For 2 or 3 extra dimensions PBHs with mass $\sim 2000 M_\odot$ can occur and may act as both dark matter and seeds for early galaxy and QSO formation.

Contributions from the G1 Working Group at the APS Summer Study on Particle and Nuclear Astrophysics and Cosmology in the Next Millennium, Snowmass, Colorado, June 29 - July 14, 1994. V. Frolov and L. Thorlacius: Quantum Aspects of Gravity. S.B. Giddings and L. Thorlacius: Introduction to the Information Problem. A. Strominger: Two-Dimensional Black Holes and the Information Puzzle. V. Frolov: Entropy of Black Holes. L. Thorlacius: Black Hole Complementarity. D.A. Lowe: Causality in String Theory. A.O. Barvinski: Nonlocal Effective Action and Black Holes. P.C. Argyres: Universality and Scaling in Black Hole Formation.