ABSTRACT We present a sample of 151 massive (M* > 1010 M⊙) quiescent galaxies at 2 < z < 5, based on a sophisticated Bayesian spectral energy distribution fitting analysis of the CANDELS UDS and GOODS-South fields. Our sample includes a robust sub-sample of 61 objects for which we confidently exclude low-redshift and star-forming solutions. We identify 10 robust objects at z > 3, of which 2 are at z > 4. We report formation redshifts, demonstrating that the oldest objects formed at z > 6; however, individual ages from our photometric data have significant uncertainties, typically ∼0.5 Gyr. We demonstrate that the UVJ colours of the quiescent population evolve with redshift at z > 3, becoming bluer and more similar to post-starburst galaxies at lower redshift. Based upon this, we construct a model for the time evolution of quiescent galaxy UVJ colours, concluding that the oldest objects are consistent with forming the bulk of their stellar mass at z ∼ 6–7 and quenching at z ∼ 5. We report spectroscopic redshifts for two of our objects at z = 3.440 and 3.396, which exhibit extremely weak Ly α emission in ultra-deep VANDELS spectra. We calculate star formation rates based on these line fluxes, finding that these galaxies are consistent with our quiescent selection criteria, provided their Ly α escape fractions are >3 and >10 per cent, respectively. We finally report that our highest redshift robust object exhibits a continuum break at λ ∼ 7000 Å in a spectrum from VUDS, consistent with our photometric redshift of $z_\mathrm{phot}=4.72^{+0.06}_{-0.04}$. If confirmed as quiescent, this object would be the highest redshift known quiescent galaxy. To obtain stronger constraints on the times of the earliest quenching events, high-SNR spectroscopy must be extended to z ≳ 3 quiescent objects.