Born in Tennessee, Stone was the son of Asher and Judith Stone, natives of Virginia. He did not attend college since his family was fairly poor, but he studied a great deal and eventually taught school. In 1855, he moved to Tishomingo County, Mississippi and became a station agent at Iuka when the Memphis and Charleston railroad opened.
With the outbreak of the War Between the States in 1861, Stone enlisted in the Confederate Army that April. He commanded Company K of the Second Mississippi Infantry and saw action in Virginia. Stone, who had the rank of colonel, was placed in command of another regiment due to a reorganization in 1862. Colonel Stone was offered a promotion to major general, but he declined since it meant leaving his regiment. He and his unit were captured in early 1865 and held prisoner in Kentucky, Camp Chase, Ohio, and then finally Johnson Island, Ohio.
At the end of the war, Stone returned back to Tishomingo County and was elected mayor and treasurer. In 1869, he won a race to become a state senator, winning re-election in 1873. Governor Adelbert Ames resigned in 1876, making Stone, the President Pro Tempore of the Mississippi Senate, the acting governor. He won the office in his own right as a Democrat in the 1877 election, but was defeated by Robert Lowry in 1881. Stone became governor again after winning the 1889 election and his term was extended (ending in 1896) by the state constitution of 1890.
He married Mary G. Coman in 1872; the couple had two children that died at a young age. They did, however, adopt three children of John's brother and raised them as their own. Stone died in Holly Springs in 1900, at the age of 69.
Stone County, Mississippi is named in honor of him.
See also: Governor of Mississippi