We consider proton decay in theories that contain large extra dimensions. I
f virtual black hole states are allowed by the theory, as is generally the
case, then proton decay can proceed via virtual black holes. The experiment
al limits on the proton lifetime place strong constraints on the quantum gr
avity scale M-qg (the effective Planck mass). For most theories, this impli
es a lower bound of Mqg > 10(16) GeV. The corresponding bound on the size o
f large extra dimensions is l < 10(6/n) x 10(-30) cm, where n is the number
of such dimensions. Regrettably for most theories this limit rules out the
possibility of observing large extra dimensions at accelerators or in mill
imeter scale gravity experiments. Conversely, proton decay could be dominat
ed by virtual black holes, providing an experimental probe to study stringy
quantum gravity physics.