We present the Red MSX Source (RMS) Survey, the largest statistically selected catalog of young massive protostars and HII regions to date. We outline the construction of the catalog using mid and near infrared color selection, as well as the detailed follow up work at other wavelengths, and at higher spatial resolution in the infrared. We show that within the adopted selection bounds we are more than 90% complete for the massive protostellar population, with a positional accuracy of the exciting source of better than 2 arcseconds. We briefly summarize some of the results that can be obtained from studying the properties of the objects in the catalog as a whole, and find evidence that the most massive stars form: (i) preferentially nearer the Galactic centre than the anti-centre; (ii) in the most heavily reddened environments, suggestive of high accretion rates; and (iii) from the most massive cloud cores.