Context: The Red MSX Source (RMS) survey is an ongoing multi-wavelength observational programme designed to return a large, high-resolution mid-infrared colour-selected sample of massive young stellar objects. 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 allow us to identify and remove nearby low-mass YSOs and help in identifying evolved stars which are weak CO emitters. Method: We have used the 15 m James Clerk Maxwell Telescope (JCMT), the 13.7 m telescope of the Purple Mountain Observatory (PMO), the 20 m Onsala telescope and the 22m Mopra telescope to conduct molecular line observations towards 508 MYSOs candidates located in the 1st and 2nd Quadrants. Results: We detect 13CO emission towards 780 RMS sources which corresponds to approximately 84% of those observed (911). A total of 2595 emission components are detected above 3sigma level (typically T^*_{rm{A}} > 0.3K), with multiple components being observed towards the majority of these sources -- 520 sources (~56%) -- with an average of ~4 molecular clouds detected along each line of sight. We have used archival CS (J=2-1) and maser velocities to resolve the component multiplicity towards 175 sources (~20%) and have derived a criterion which is used to identify the most likely component for a further 191 multiple component sources. Combined with the single component detections we have obtained unambiguous kinematic velocities for 638 of the 780 MYSOs candidates towards which CO is detected (~80% of the detections). Using the Galactic rotation curve we calculate kinematic distances for all detected components.