Leirstein har hatt kommunale og fylkeskommunale verv siden 1991. Han var varaordfører i Moss 1999–2003, formann i Fremskrittspartiets Ungdom 1994–1995 og var medlem av sentralstyret i Fremskrittspartiet 2003–2011.
12. januar 2018 trakk Leirstein seg som parlamentarisk nestleder og justispolitisk talsmann i Frp etter beskyldninger om seksuell trakassering.[4][5]
26. april 2019 meldte Leirstein seg ut av Fremskrittspartiet.[6] Han vil dermed sitte på Stortinget som uavhengig representant resten av stortingsperioden.