Bruce was born in Farmville, Virginia, and moved to Missouri after becoming a printer's apprentice. He attended Oberlin college in Ohio and worked as steamboat porter on the Mississippi River. In 1864 he moved to Hannibal, Missouri, where he established Missouri's first school for blacks.
In 1871, he ran for sheriff in Bolivar County, Mississippi and won the election. He was elected to the Senate in February 1874. In 1880, James Z. George was elected to succeed Bruce as Mississippi's representative.