Holliday won the election for Governor of Virginia in 1877 as a Conservative Democrat unopposed. Holliday began his term by breaking the established tradition of small inauguration ceremonies for Virginia governors. His ceremony included parades, bands, cannons, and an inaugural speech given to some 10,000 people.
Holliday traveled the world after his term as Governor. He died in 1899 and was buried in Mount Hebron Cemetery in Winchester, Virginia.