Coleman was selected by NASA in March 1992 and reported to the Johnson Space Center in August 1992. Initially assigned to the Astronaut Office Mission Support Branch and detailed to flight software verification in the Shuttle Avionics Integration Laboratory, Coleman subsequently served as the special assistant to the Center Director, Johnson Space Center. She trained as STS-83 backup mission specialist to Dr. Don Thomas when he suffered a broken right ankle following the conclusion of a routine training exercise. Presently, Coleman is assigned to the Astronaut Office Payloads and Habitability Branch. She works with experiment designers to insure that payloads can be operated successfully in the microgravity environment of low earth orbit, and is the lead astronaut for long term space flight habitability issues, such as accoustics and living accommodations aboard the International Space Station.
From October 20 to November 5, 1995, Coleman served as a mission specialist aboard Space Shuttle Columbia on STS-73, the second United States Microgravity Laboratory mission. The mission focused on materials science, biotechnology, combustion science, the physics of fluids, and numerous scientific experiments housed in the pressurized Spacelab module. In completing her first space flight, Coleman orbited the Earth 256 times, traveled over 6 million miles, and logged a total of 15 days, 21 hours, 52 minutes and 21 seconds in space.