After a brief education in Boston under the care of his older sister Ellen, Randolph served in the United States Navy from 1831-1839 and obtained his law degree from the University of Virginia in 1841. He practiced law in Albemarle County until 1851, when he moved to Richmond. There he had a successful law practice, served on the Richmond City Council, was an officer of the Virginia Historical Society, and was, briefly, a state senator for the City of Richmond under secession. On April 2o, 1852, Randolph married Mary Elizabeth Adams Pope, a wealthy widow, and took up residence in one of Richmond's elite neighborhoods. The couple had no children.
Randolph was elected to the 1861 Virginia Convention as a secessionist and served with the Richmond Howitzers, a company he founded in response to the John Brown raid at Harper's Ferry and which remains in existence today. Randolph eventually rose to the rank of Confederate Brigadier General and was nominated as the Confederate secretary of war on March 17, 1862, but constant conflict with Jefferson Davis and Randolph's own poor health led him to resign on November 15, 1862.