Herrington received his commission from Aviation Officer Candidate School in March 1984 and was designated a Naval Aviator in March 1985. He reported to Patrol Squadron Thirty-One (VP-31) at the Moffett Field Naval Air Station, Mountain View, California for initial training in the P-3C Orion. His first operational assignment was with Patrol Squadron Forty-Eight (VP-48) where he made three operational deployments, two to the Northern Pacific based from Naval Air Station Adak, Alaska and one to the Western Pacific based from the Naval Air Station Cubi Point, Republic of the Philippines. While assigned to VP-48, Herrington was designated a Patrol Plane Commander, Mission Commander, and Patrol Plane Instructor Pilot. Following completion of his first operational tour, Herrington then returned to VP-31 as a Fleet Replacement Squadron Instructor Pilot. While assigned to VP-31 he was selected to attend the U.S. Naval Test Pilot School in Patuxent River, Maryland in January 1990. After graduation in December, 1990, he reported to the Force Warfare Aircraft Test Directorate as a project test pilot for the Joint Primary Aircraft Training System. Herrington conducted additional flight test assignments flying numerous variants of the P-3 Orion as well as the T-34C and the DeHavilland Dash 7. Following his selection as an Aeronautical Engineering Duty Officer, Herrington reported to the U.S. Naval Postgraduate School where he completed a master of science degree in aeronautical engineering in June 1995. Herrington was assigned as a special projects officer to the Bureau of Naval Personnel Sea Duty Component when selected for the astronaut program.
He has logged over 2,300 flight hours in over 30 different types of aircraft.