Kelly received his commission from the U.S. Merchant Marine Academy in June 1986, and was designated a Naval Aviator in December 1987. He then reported to Attack Squadron 128 at Naval Air Station (NAS) Whidbey Island, Oak Harbor, Washington, for initial training in the A-6E Aircraft. Upon completion of this training, he was assigned to Attack Squadron 115 based in Atsugi, Japan. While assigned to Attack Squadron 115 he made two deployments to the Persian Gulf aboard the USS Midway. During his second deployment he flew 39 combat missions in Operation Desert Storm. During this tour he was designated an Airwing Qualified Landing Signals Officer (LSO). Kelly was selected for the Naval Post Graduate School/Test Pilot School Cooperative Education Program in July 1991. He completed 15 months of graduate work at Monterey, California, before attending the U.S. Naval Test Pilot School in June 1993. After graduating in June 1994, he worked as a project test pilot at the Carrier Suitability Department of the Strike Aircraft Test Squadron, Naval Air Warfare Center, Patuxent River, Maryland, flying the A-6E, EA-6B and F-18 aircraft. Kelly was assigned to the U.S. Naval Test Pilot School as an instructor pilot in the F-18, T-38 and T-2 aircraft when selected for the astronaut program.
He has logged over 2,000 flight hours in more than 40 different aircraft and has over 375 carrier landings.