Nathman has served in a variety of sea, shore and joint assignments, and flown over 40 different types of aircraft during his career. At sea, he flew the F-4 Phantom II with Fighter Squadron Two Thirteen (VF-213) and the F-14 Tomcat with Fighter Squadron Fifty-One (VF-51). He then transitioned to the F/A-18 Hornet, subsequently commanding Strike Fighter Squadron One Thirty-Two (VFA-132) and leading his squadron in the first F/A-18 combat sorties against Libya in 1986. Nathman reported to the aircraft carrier USS Nimitz (CVN-68) in 1987 as executive officer, and subsequently assumed command of USS La Salle (AGF-3), the flagship for Commander, Middle East Force (COMIDEASTFOR), during Operations Desert Shield and Desert Storm. Nathman returned to the USS Nimitz (CVN-68) as its commanding officer from 1992 to 1994.
Upon his selection to flag rank in 1994, Nathman served on the NATO staff of Commander, Allied Forces Southern Europe (AF SOUTH), and as Director of Logistics for Commander, NATO Implementation Force (IFOR) during its first out-of-area deployment to Bosnia. In 1996, he commanded Carrier Group Seven, NIMITZ Carrier Strike Group and Battle Force FIFTY in the Persian Gulf. Nathman subsequently served as Director, Air Warfare, on the Chief of Naval Operations staff in Washington, D.C. In August 2000, he took command of Naval Air Force, United States Pacific Fleet and was designated Commander, Naval Air Forces in October 2001. In August 2002, Nathman was assigned as the Deputy Chief of Naval Operations for Warfare Requirements and Programs (N6/N7) at the Pentagon.
On 2 October 2008, Nathman published a commentary in the Virginian-Pilot praising presidential candidate Barack Obama. In February 2012, he was named a co-chair of the re-election campaign of President Obama. On 6 September 2012, Nathman spoke at the 2012 Democratic National Convention.In July 2022, he joined with other former U.S. military leaders in condemning former president and commander in chief, Donald Trump. "While rioters tried to thwart the peaceful transfer of power and ransacked the Capitol on Jan. 6, 2021, the president and commander in chief, Donald Trump, abdicated his duty to preserve, protect and defend the Constitution.[2]