Born in Richmond, Virginia, Paine moved with his parents to Milledgeville, Georgia, in 1827.
He entered the Confederate States Army and served as captain in the First Georgia Regiment throughout the Civil War.
He moved to Savannah, Georgia, at the close of the Civil War and continued the practice of law.
Paine was elected as a Democrat to the Forty-first Congress to fill the vacancy caused by the House declaring Joseph W. Clift not entitled to the seat, and served from December 22, 1870, to March 3, 1871.
This article incorporates public domain material from the Biographical Directory of the United States Congress