Admitted to the bar in 1850, Key practiced law in Chattanooga and became active in Democratic politics. In 1856 he stood as a presidential elector for James Buchanan and four years later for John C. Breckinridge. An opponent of secession, he worked to keep Tennessee in the Union but remained loyal to his state once it joined the Confederacy. In 1861 he was commissioned an officer in the Confederate Army, rising to the rank of lieutenant colonel by war's end. At Vicksburg (1862) he was wounded and taken prisoner.

After the war Key worked to heal sectional grievances and restore the Union. In 1870 he was a delegate to the Tennessee state constitutional convention and was elected a state chancellor. He was appointed to the U.S. Senate (1875), succeeding former president Andrew Johnson, but two years later was defeated in a bid to retain the seat. In the disputed presidential election of 1876, Key supported Samuel J. Tilden over Rutherford B. Hayes (Hayes, Rutherford B.). When the election was turned over to a specially appointed electoral commission, Hayes—in return for Southern support—promised, among other things, that he would name a Southern Democrat to a post in his Cabinet. Hayes's intent had been to appoint the Confederate general Joseph E. Johnston as secretary of war; but the proposal drew such heated criticism within his own party that he settled on Key, a less prominent representative of the Confederacy, whom he in 1877 appointed postmaster general. Key resigned in 1880 to accept a seat on the U.S. District Court in Tennessee, where he served until his retirement in 1894. As a jurist he was noted for seeking justice rather than for adhering to the strict letter of the law.