We discuss phenomenological and cosmological implications and constraints for theories with TeV scale quantum gravity. In these theories smallness of the Newtonian constant is due to the presence of two or more new dimensions of sub-millimeter size, with the standard model fields localized on a 3-brane in the higher dimensional space. Constraints arise both from quantum gravitational effects at the TeV scale and from the production of higher dimensional gravitons in different processes (e.g. star cooling). We also explore some novel phenomena resulting from the existence of states propagating in the higher dimensional bulk.