He served in the Union Army during the Civil War. He was appointed lieutenant colonel of the Forty-second Regiment, Ohio Volunteer Infantry, November 27, 1861, and promoted to the rank of colonel March 14, 1862. He settled in New Orleans, Louisiana, and practiced law from 1864 to 1879.
Sheldon was elected as a Republican to the Forty-first, Forty-second, and Forty-third Congresses (March 4, 1869-March 3, 1875). He served as chairman of the Committee on Militia (Forty-second Congress). He was an unsuccessful candidate for reelection in 1874 to the Forty-fourth Congress. He returned to Ohio in 1879.