Randolph studied law and moral and natural philosophy at the University of Virginia, 1829-1831, but chose to pursue a career on the western frontier. He worked briefly as a clerk for the Department of State before being appointed Secretary of the Arkansas Territory by President Andrew Jackson in February 1835, a position Randolph held through the transition to statehood. On April 9, 1835, he married Elizabeth Martin, daughter of James Glasgow Martin of Nashville, and grandniece to President Jackson. They had one son, Lewis Jackson Randolph (1836-1840).
After his commission expired, Randolph began purchasing large tracts of land, eventually acquiring over ten thousand acres. He died of malaria in Clark County, Arkansas, on September 24, 1837, and was buried on his newly established plantation, Terre Noir.