Williams received her commission as an Ensign in the United States Navy from the United States Naval Academy in May 1987. After a six-month temporary assignment at the Naval Coastal System Command, she received her designation as a Basic Diving Officer and then reported to Naval Aviation Training Command. She was designated a Naval Aviator in July 1989. She then reported to Helicopter Combat Support Squadron 3 for initial H46, Seaknight, training. Upon completion of this training, she was assigned to Helicopter Combat Support Squadron 8 in Norfolk, Virginia, and made overseas deployments to the Mediterranean, Red Sea and the Persian Gulf in support of Desert Shield and Operation Provide Comfort. In September 1992 she was the Officer-in-Charge of an H-46 detachment sent to Miami, Florida for Hurricane Andrew Relief Operations onboard USS Sylvania. Williams was selected for United States Naval Test Pilot School and began the course in January 1993. After graduation in December 1993, she was assigned to the Rotary Wing Aircraft Test Directorate as an H-46 Project Officer, and V-22 Chase Pilot in the T-2. While there she was also assigned as the squadron Safety Officer and flew test flights in the SH-60B/F, UH-1, AH-1W, SH-2, VH-3, H-46, CH-53 and the H-57. In December 1995, she went back to the Naval Test Pilot School as an Instructor in the Rotary Wing Department and the school's Safety Officer. There she flew the UH-60, OH-6 and the OH-58. From there she was assigned to the USS Saipan (LHA-2), Norfolk, Virginia, as the Aircraft Handler and the Assistant Air Boss. Williams was deployed onboard USS Saipan when she was selected for the astronaut program.
She has logged over 2300 flight hours in more than 30 different aircraft.