We recently proposed a solution to the hierarchy problem not relying on low-energy supersymmetry or technicolor. Instead, the problem is nullified by bringing quantum gravity down to the TeV scale. This is accomplished by the presence of \(n \geq 2\) new dimensions of sub-millimeter size, with the SM fields localised on a 3-brane in the higher dimensional space. In this paper we systematically study the experimental viability of this scenario. Constraints arise both from strong quantum gravitational effects at the TeV scale, and more importantly from the production of massless higher dimensional gravitons with TeV suppressed couplings. Theories with \(n>2\) are safe due mainly to the infrared softness of higher dimensional gravity. For \(n=2\), the six dimensional Planck scale must be pushed above \(\sim 30\) TeV to avoid cooling SN1987A and distortions of the diffuse photon background. Nevertheless, the particular implementation of our framework within type I string theory can evade all constraints, for any \(n \geq 2\), with string scale \(m_s \sim 1\) TeV. We also explore novel phenomena resulting from the existence of new states propagating in the higher dimensional space. The Peccei-Quinn solution to the strong CP problem is revived with a weak scale axion in the bulk. Gauge fields in the bulk can mediate repulsive forces \(\sim 10^6 - 10^8\) times stronger than gravity at sub-mm distances, and may help stabilize the proton. Higher-dimensional gravitons produced on our brane and captured on a different "fat" brane can provide a natural dark matter candidate.