We report nuclear magnetic resonance (NMR) results on water saturated, dense, nano-crystalline YSZ samples (9.5 mol% yttria doped zirconia) which exhibit proton conductivity at temperatures as low as room temperature. 1H-NMR spectra recorded under static and magic angle spinning conditions show two distinct signals. Their temperature-dependent behavior and their linewidths suggest that one can be attributed to (free) water adsorbed on the surface of the sample and the other one to mobile protons within the sample. This interpretation is supported by comparison with measurements on a single-crystalline sample. For the nano-crystalline samples motional narrowing is observed for the signal originating from protons in the sample interior. For these protons, the analysis of temperature and field dependent spin-lattice relaxation time T1 points towards diffusion in a confined two-dimensional geometry. We attribute this quasi two-dimensional motion to protons that are mobile along internal interfaces or nanopores of nano-crystalline YSZ. © 2013 The Owner Societies.