Context.The Red MSX Source (RMS) survey is an ongoing multi-wavelength observational programme designed to return a large, well-selected sample of massive young stellar objects (MYSOs). We have identified ~2000 MYSOs candidates located within our Galaxy by comparing the colours of MSX and 2MASS point sources to those of known MYSOs. The aim of our follow-up observations is to identify other contaminating objects such as ultra compact (UC) HII regions, evolved stars and planetary nebulae (PNe) and distinguish between genuine MYSOs and nearby low-mass YSOs. Aims.A critical part of our follow-up programme is to conduct 13CO molecular line observations in order to determine kinematic distances to all of our MYSO candidates. These distances will be used in combination with far-IR and (sub)millimetre fluxes to determine bolometric luminosities which will allow us to identify and remove nearby low-mass YSOs. In addition these molecular line observations will help in identifying evolved stars which are weak CO emitters. Methods.We have used the 22 m Mopra telescope, the 15 m JCMT and the 20 m Onsala telescope to conduct molecular line observations towards 854 MYSOs candidates located in the 3rd and 4th quadrants. These observations have been made at the J = 1-0 (Mopra and Onsala) and J = 2-1 (JCMT) rotational transition frequency of 13CO molecules and have a spatial resolution of ~20´´-40´´, a sensitivity of $T_{\rm {A}}^*$ $\simeq$ 0.1 K and a velocity resolution of ~0.2 km s-1. Results.We detect 13CO emission towards a total of 752 of the 854 RMS sources observed (~88%). In total 2132 emission components are detected above 3$\sigma$ level (typically $T^*_{\rm {A}} \ge 0.3$ K). Multiple emission profiles are observed towards the majority of these sources - 461 sources (~60%) - with an average of ~4 molecular clouds detected along the line of sight. These multiple emission features make it difficult to assign a kinematic velocity to many of our sample. We have used archival CS (J = 2-1) and maser velocities to resolve the component multiplicity towards 82 sources and have derived a criterion which is used to identify the most likely component for a further 218 multiple component sources. Combined with the single component detections we have obtained unambiguous kinematic velocities towards 591 sources (~80% of the detections). The 161 sources for which we have not been able to determine the kinematic velocity will require additional line data. Using the rotation curve of Brand & Blitz (1993) and their radial velocities we calculate kinematic distances for all components detected.