The outer reaches of our Solar System are home to hundreds of thousands of small icy worlds. Their present orbits are a sculpted signature of the early migrations of the giant planets, particularly Neptune. Yet the faintness and highly eccentric orbits of most of these worlds mean only a tiny fraction of them have yet been discovered. With the Outer Solar System Origins Survey on CFHT, we are discovering up to five hundred new outer Solar System objects, with exquisitely well-determined orbital parameters. Our complementary Large Program on Gemini North is observing the brightest of our discoveries in the optical and infrared with unprecedented precision, providing information on the ices, silicates and organic compounds on the surfaces of these small worlds. This colourful map of the structure of the outer Solar System is providing new constraints on Neptune's migration.