Measuring the water diffusivity in porous building materials with NMR is hindered by the presence of large internal magnetic field gradients originating from magnetic impurities (Fe). To investigate the diffusion of water in these materials, a stimulated echo NMR technique is applied. A new analytical equation for the long-time signal decay in the presence of spatially varying internal field gradients is derived. This equation is experimentally confirmed by measurements on representative materials with large internal gradients (fired-clay brick and sintered crushed glass) and a material with very small internal gradients (glass filter). The diffusivity is determined in the long time limit, where it is constant and limited by the tortuosity of the pore structure. Tortuosities of different samples derived from the NMR data show an excellent agreement with the macroscopic tortuosities measured by electrochemical impedance spectroscopy. The developed technique can also be applied in unsaturated media, during e.g., drying, water absorption, and concentration changes. The characteristic length scales of the internal field fluctuations estimated from the model are compared with the structural length scales, whereas the magnitude of these fluctuations is compared with results of macroscopic magnetization measurements.