Recently it was proposed that the standard model (SM) degrees of freedom reside on a $(3+1)$-dimensional wall or ``3-brane'' embedded in a higher-dimensional spacetime. Furthermore, in this picture it is possible for the fundamental Planck mass $\mst$ to be as small as the weak scale $\mst\simeq O(\tev)$ and the observed weakness of gravity at long distances is due the existence of new sub-millimeter spatial dimensions. We show that in this picture it is natural to expect neutrino masses to occur in the $10^{-1} - 10^{-4}\ev$ range, despite the lack of any fundamental scale higher than $\mst$. Such suppressed neutrino masses are not the result of a see-saw, but have intrinsically higher-dimensional explanations. We explore two possibilities. The first mechanism identifies any massless bulk fermions as right-handed neutrinos. These give naturally small Dirac masses for the same reason that gravity is weak at long distances in this framework. The second mechanism takes advantage of the large {\it infrared} desert: the space in the extra dimensions. Here, small Majorana neutrino masses are generated by breaking lepton number on distant branes.

17 pages, latex