Randolph was born in Richmond, Virginia, the son of Peyton and Maria Ward Randolph. He was also the grandson of Edmund Jennings Randolph and grandnephew of another Peyton Randolph.^[1]

Randolph attended the College of William and Mary, and studied law at the University of Virginia. He moved to New Orleans, studying or practicing law there until 1849. He clerked for the US Circuit of Louisiana. After arriving in California in 1849, he practiced law and was elected to the first State Assembly of California.^[1]

Randolph collaborated with William Walker to seize control of Nicaragua in 1855 and 1856. In 1855, Randolph garnered the support of agents of the Accessory Transit Company to give in-kind aid to the filibuster of William Walker. Walker collaborated with the Liberal faction of Nicaragua's split-government to overthrow the Conservative faction and gain control of the country. Randolph, an old friend Walker's, hatched a plan to gain the cooperation of Cornelius K. Garrison and Charles Morgan of the Accessory Transit Company to provide transportation for mercenaries and supplies to Walker in Nicaragua. In exchange, Walker agreed to invalidate the old transit charter for Accessory Transit Company and reassign those rights to Randolph. Walker agreed to re-appropriate property of the Accessory Transit Company to Garrison and Morgan, while Randolph would sell the transit charter to them.^[2]

• Randolph Oration on the California Pioneer
• Filibusters and Financiers: The Story of William Walker and His Associates