Pat Mullins unsuccessfully ran for a position on the Fairfax County Board of Supervisors in 1979 and 1987. He served as Chairman of the Fairfax County Republican Committee from 1990 to 1996. After moving to Louisa County, he served as the Chairman of the Louisa County Republican Committee from 2008-2009, after which he was elected as chair of the Republican Party of Virginia.
Pat Mullins was elected as temporary party Chairman on May 2, 2009, to replace Jeff Frederick, who had been fired as Chairman in April. He was elected as full-time Chairman to serve the remainder of Frederick's term on May 30, 2009, and was re-elected in 2012.