Randolph efterträdde 1869 Marcus Lawrence Ward som guvernör i New Jersey. Han efterträddes tre år senare av Joel Parker. Han efterträdde 1875 John P. Stockton som senator för New Jersey. Han var ordförande i senatens militärutskott 1879-1881. Han efterträddes som senator av William Joyce Sewell.