We present results of an extensive search for molecular gas in 14 high redshift ($z>2$) radio galaxies. Radio galaxies with redshifts between 2.0 and 4.3 were observed during several sessions on two different single-dish telescopes (IRAM and JCMT) and two interferometric arrays (VLA and OVRO). No significant CO emission to a 2$\sigma$ limit of a few times 10^{10} K km s^{-1} pc^2 was detected in any of these objects. The limits on the CO emission achieved indicate that, assuming a CO-H$_2$ conversion factor similar to the Galactic value, the mass of enriched molecular gas in these galaxies is less than $10^{11} $M$_{\odot}$. This suggests that distant radio galaxies may not be forming stars at the extremely high rates that have earlier been proposed, although they may still be forming stars at rates comparable to those of local starburst galaxies.