[2] In 1871 voters from Sussex and adjoining Dinwiddie and Greensville Counties elected Stevens to the Senate of Virginia to replace white Republican David G. Carr.

In 1874, he was joined in the Virginia Senate by Joseph P. Evans, who had been born a slave in Dinwiddie County, then won elected to the House of Delegates in 1871, and then in 1874 won an election to represent Petersburg to the Virginia Senate.

However, Evans became embroiled in a conflict with Petersburg's Republican boss, former Confederate General William Mahone and lost the next election.

Nonetheless, in the changing racial politics of as the century closed, Stevens lost the election of 1879 to Samuel Pickett.

[3] One contemporary called Stevens an "able and scholarly man" and noted his speech had "elegance and grace.