In 1982, his book The Hidden West: Journey in the American Outback was published. It was described by a New York Times review as "A celebration of that vast expanse of remaining American frontier."

In 1992, Schultheis' book Night Letters: Inside Wartime Afghanistan, was published, on the topic of the Soviet war in Afghanistan, which he covered in person as a journalist. A Library Journal review states "His descriptions of the many individuals and their savage landscape are unforgettable, and his tales of the desperate yet eager combat by a remarkably resilient people give some of the most vivid images of that war available to us in the West." A review in Publisher's Weekly states, "In this chronicle of high adventure Schultheis succeeds in conveying his exhilaration to the reader."

Waging Peace: A Special Operations Team's Battle to Rebuild Iraq (2005), was written after Schultheis spent six months in 2004 as an embedded journalist with a US. Army Civil Affairs team who was tasked with working on rebuilding operations in a Shi'ite neighborhood in Baghdad, during the Iraq war. One review calls the book "amusing as well as surprising", and goes on to say, "there's valuable information here about the unsung heroes who do the dirty work required to help push Iraqis toward a better life and democracy."

In Hunting Bin Laden: How al-Qaeda Is Winning the War on Terror (2008), Schultheis questions the military tactics in the wars in both Iraq and Afghanistan. One review calls it "one of the rawest accounts of Afghanistan's suffering to emerge from a growing library documenting the country's misery."