After college he joined Army Times. Naylor's beats have included U.S. Army training, readiness and the service's senior leadership. He has covered the military in Pakistan, Somalia and Haiti.
In 1995, Naylor co-wrote his first book, Clash of Chariots: The Great Tank Battles. In January 2002, the 101st Airborne Division (Air Assault) took a couple dozen journalists, including Naylor, into Afghanistan with Task Force Rakkasan. Naylor spent almost four months covering the War in Afghanistan, including several days in the Shah-i-Kot Valley at the start of Operation Anaconda. He returned to the valley at the end of the operation with 10th Mountain Division troops. He was one of eight journalists allowed to accompany the troops into battle during Operation Anaconda and spent the following three years interviewing almost 200 participants and accessed secret documents that explained the full role of the Advance Force Operations in Operation Anaconda. With this information, Naylor wrote his second book, Not a Good Day to Die: The Untold Story of Operation Anaconda, published in 2005. In 2015, his book Relentless Strike: The Secret History of Joint Special Operations Command was published by St. Martin's Press.