For many pathologies, early structural tissue changes occur at the cellular level, on the scale of micrometers or tens of micrometers. Magnetic resonance imaging (MRI) is a powerful non-invasive imaging tool used for medical diagnosis, but its clinical hardware is incapable of reaching the cellular length scale directly. In spite of this limitation, microscopic tissue changes in pathology can potentially be captured indirectly, from macroscopic imaging characteristics, by studying water diffusion. Here we focus on water diffusion and NMR relaxation in the human prostate, a highly heterogeneous organ at the cellular level. We present a physical picture of water diffusion and NMR relaxation in the prostate tissue, that is comprised of a densely-packed cellular compartment (composed of stroma and epithelium), and a luminal compartment with almost unrestricted water diffusion. Transverse NMR relaxation is used to identify fast and slow T₂ components, corresponding to these tissue compartments, and to disentangle the luminal and cellular compartment contributions to the temporal evolution of the overall water diffusion coefficient. Diffusion in the luminal compartment falls into the short-time surface-to-volume (S/V) limit, indicating that only a small fraction of water molecules has time to encounter the luminal walls of healthy tissue; from the S/V ratio, the average lumen diameter averaged over three young healthy subjects is measured to be 217.7 ± 188.7 μm. Conversely, the diffusion in the cellular compartment is highly restricted and anisotropic, consistent with the fibrous character of the stromal tissue. Diffusion transverse to these fibers is well described by the random permeable barrier model (RPBM), as confirmed by the dynamical exponent ϑ = 1/2 for approaching the long-time limit of diffusion, and the corresponding structural exponent p = −1 in histology. The RPBM-derived fiber diameter and membrane permeability were 19.8 ± 8.1 μm and 0.044 ± 0.045 μm/ms, respectively, in agreement with known values from tissue histology and membrane biophysics. Lastly, we revisited 38 prostate cancer cases from a recently published study, and found the same dynamical exponent ϑ = 1/2 of diffusion in tumors and benign regions. Our results suggest that a multi-parametric MRI acquisition combined with biophysical modeling may be a powerful non-invasive complement to prostate cancer grading, reducing the need for biopsies.