Gordon joined NASA with fourteen other astronuts in 1963. His first flight three years later was aboard Gemini XI as Pilot with Commander Charles Conrad, Jr., during which the team set an altitude record of 850 nautical miles above the Earth. He also accumulated 2 hours and 44 minutes of E.V.A. time during the same mission. Three years after that, Gordon would serve as the Command Module Pilot (CMP) for Apollo XII while his two crewmates, Conrad (CDR) and Bean (LMP), explored the region of the Moon known as the Ocean of Storms.