The pure rotational spectra of the van der Waals dimers of Ne, Kr, and Xe with CO have been measured using a pulsed jet, cavity microwave Fourier transform spectrometer. All transitions measured were a-type R-branches, obeying selection rules Delta J=+1, Delta K-a=0, and Delta K-c=+1. Spectra with K-a=0 were measured for 7 isotopomers of Ne-CO, 13 of Kr-CO, and 17 of Xe-CO. Transitions with K-a=1 were measured for Ne-20-(CO)-C-12-O-16 and Kr-84-(CO)-C-12-O-16. Rotational constants and centrifugal distortion constants have been determined for all species, as well as the O-17 quadrupole coupling constants chi(aa) for Kr-84-(CO)-C-13-O-17 and Ne-20-(CO)-C-13-O-17. Effective structural parameters have been calculated from the rotational constants. Results derived from the O-17 quadrupole coupling constants and centrifugal distortion constants indicate that Ne-CO is considerably more flexible than Ar-CO, Kr-CO, or Xe-CO. Failure to observe hyperfine structure due to the Ne-21, Kr-83, and Xe-131 nuclei is discussed in terms of the weak rare gas-CO bonding. Comparisons have been made to the isoelectronic rare gas-N-2 van der Waals complexes.