We present the redshift distribution of the SHADES galaxy population based on the rest-frame radio-mm-FIR colours of 120 robustly detected 850um sources in the Lockman Hole East (LH) and Subaru XMM-Newton Deep Field (SXDF). The redshift distribution derived from the full SED information is shown to be narrower than that determined from the radio-submm spectral index, as more photometric bands contribute to a higher redshift accuracy. The redshift distribution of sources derived from at least two photometric bands peaks at z ~ 2.4 and has a near-Gaussian distribution, with 50 per cent (interquartile range) of sources at z=1.8-3.1. We find a statistically-significant difference between the measured redshift distributions in the two fields; the SXDF peaking at a slightly lower redshift (median z ~ 2.2) than the LH (median z ~ 2.7), which we attribute to the noise-properties of the radio observations. We demonstrate however that there could also be field-to-field variations that are consistent with the measured differences in the redshift distributions, and hence, that the incomplete area observed by SHADES with SCUBA, despite being the largest sub-mm survey to date, may still be too small to fully characterize the bright sub-mm galaxy population. Finally we present a brief comparison with the predicted, or assumed, redshift distributions of sub-mm galaxy formation and evolution models, and we derive the contribution of these SHADES sources and the general sub-mm galaxy population to the star formation-rate density at different epochs.