Fayette McMullen was born on May 18, 1805 at Estillville (now Gate City) in Scott County. He attended private schools and was a stage driver by profession. McMullen was a member of the State Senate for the Washington district from 1839-1849. He was elected as a Democrat to the 31st Congress and to the three succeeding Congresses, serving from 1849-1857. McMullen was popular with the public. He was known for never missing a chance to shake hands with voters and liked to give speeches at any public gathering.

He was appointed by President Buchanan as Governor of the Washington Territory from 1857-1861. During the Civil War, he was elected as Representative from Virginia to the Second Confederate Congress. He served in this position until the end of the Confederacy. After the war, McMullen was an unsuccessful candidate for Congress on the Independent ticket.