The evolving pore structure of cemented paste backfill (CPB), formed from plant tailings and sand mixtures, is critical to a more thorough and complete understanding of its functionality as a support structure during mining operations. Here we employ Nuclear Magnetic Resonance (NMR) signal relaxation measurements to provide a quantitative measurement of pore size distributions in CPB samples and monitor their progression as hydration of the CBP proceeds over 28 days. Three distinct, reproducible peaks are evident in the pore size distributions, which are consistent with cement regions, the bulk of the mixture and a macro-pore backbone. All peaks reduce to smaller pore sizes with hydration time and scale with sample permeability. A novel application of these scaling laws suggest that permeability is dominated by the network of macro-pores, which constitute only 4% of the total porosity/moisture content of the samples. (C) 2013 Elsevier Ltd. All rights reserved.