Born in Tarboro, North Carolina, Shelton attended North Carolina State University, earning a degree in textiles while earning his Army commission through ROTC training. Shelton's further education includes a Master's Degree from Auburn University as well as periods studying at the Air Command and Staff College and the National War College.
Shelton served two tours of duty in Vietnam, followed by a series of command and staff assignments. Following the Gulf War, Shelton commanded the 82nd Airborne Division in his home state of North Carolina. In 1993, he was given command of XVIII Airborne Corps. Shelton led the Joint Task Force responsible for Operation Uphold Democracy in Haiti in 1994. In 1996, Shelton was promoted to the rank of general and the position of Commander in Chief of U.S. Special Operations Command (SOCOM).
Upon the resignation of John Shalikashvili, Shelton was appointed Chairman of the Joint Chiefs of Staff on 1 October 1997, a position he held until 1 October 2001, when he was succeded by Gen. Richard Myers.
In his retirement, Shelton joined the Board of Directors of Red Hat Corporation in April 2003.
Shelton created a minor controversy for 2004 Democratic presidential candidate Wesley Clark, a subordinate to Shelton during the 1999 Kosovo military actions, when he stated: "I will tell you the reason [Clark] came out of Europe early had to do with integrity and character issues, things that are very near and dear to my heart. [...] I'll just say Wes won't get my vote," casting doubt upon the presidential contender's legitimacy.
Shelton married Carolyn L. Johnson in 1963; they have three sons.