Williams was commissioned as an ensign in May 1987 and retires with the rank of Captain. From her NASA biography:
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 where 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 more than 3000 flight hours in over 30 different aircraft.