The Tully-Fisher relation (TFR) is an empirical relation between galaxy luminosity and rotation velocity. We present here the first TFR of galaxies beyond the local Universe that uses carbon monoxide (CO) as the kinematic tracer. Our final sample includes 25 isolated, non-interacting star-forming galaxies with double-horned or boxy CO integrated line profiles located at redshifts z <= 0.3, drawn from a larger ensemble of 67 detected objects. The best reverse K-s-band, stellar mass and baryonic mass CO TFRs are, respectively, M-Ks = (-8.4 +/- 2.9)[log (W-50/km s(-1)/sin i) - 2.5] + (-23.5 +/- 0.5), log (M-star/M-circle dot) = (5.2 +/- 3.0)[log (W-50/km s(-1)/sin i) - 2.5] + (10.1 +/- 0.5) and log (M-b/M-circle dot) = (4.9 +/- 2.8)[log (W-50/km s(-1)/sin i) - 2.5] + (10.2 +/- 0.5), where M-Ks is the total absolute K-s-band magnitude of the objects, M-star and M-b their total stellar and baryonic masses, and W-50 the width of their line profile at 50 per cent of the maximum. Dividing the sample into different redshift bins and comparing to the TFRs of a sample of local (z = 0) star-forming galaxies from the literature, we find no significant evolution in the slopes and zero-points of the TFRs since z approximate to 0.3, this in either luminosity or mass. In agreement with a growing number of CO TFR studies of nearby galaxies, we more generally find that CO is a suitable and attractive alternative to neutral hydrogen (HI). Our work thus provides an important benchmark for future higher redshift CO TFR studies.