John was born on September 24, 1869 at Dover, Virginia, United States, one of at least three children and the only son of General Charles Pomeroy Stone and his second wife, Annie Jeannie (Stone) Stone, from whom the son derived his double name.
General Stone, a native of Massachusetts and a graduate of West Point, had served as a Union officer in the Civil War, during which he met and married a Louisiana girl descended from a Maryland family of the same surname. His career was blighted, however, by charges of incompetence after the defeat at Ball's Bluff. Leaving the army, he became superintendent of a mining company in Virginia, but in 1870 accepted an appointment as chief of staff of the Egyptian army. From 1870 until 1883, General Stone held the post of Chief of Staff to the khedive of Egypt, and, while growing up in Cairo, John Stone Stone became fluent in Arabic, French, German and Spanish in addition to English.