The Arecibo Methanol Maser Galactic Plane Survey (AMGPS) is a blind survey for 6.7 GHz methanol masers in the Galactic Plane. 6.7 GHz methanol masers are thought to trace the very early stages of high-mass star formation, and are hence excellent tools for probing Galactic structure and understanding the formation process of massive stars. The survey targets the Galactic plane between Galactic longitudes of 35 and 55 degrees, and latitudes |b| < 0.45 degrees, and is the most sensitive blind survey done to date. I will present the first results from the survey, which was just completed in March 2006.