We present a sample of 151 massive (M_*_>10^10^M_{sun}_) 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.5Gyr. 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{alpha} 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{alpha} escape fractions are >3 and >10 per cent, respectively. We finally report that our highest redshift robust object exhibits a continuum break at {lambda}~7000{AA} in a spectrum from VUDS, consistent with our photometric redshift of z_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.