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. 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. We have used the 22m Mopra telescope, the 15m JCMT and the 20m 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 TA*≃0.1K and a velocity resolution of ∼0.2 km/s. 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σ level (typically T*A≥0.3K). 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 (1993A&A...275...67B) and their radial velocities we calculate kinematic distances for all components detected.