Mark Gordon grandit près de Kaycee, dans le nord-est du Wyoming. Après des études sur la côte est, il revient dans l'État pour gérer le ranch familial implanté comté de Johnson. Il achète ensuite d'autres fermes, ainsi qu'une librairie. Il s'investit dans la vie politique locale, siégeant dans plusieurs commissions locales puis au conseil régional de la Réserve fédérale[1].
En 2008, il se présente à la Chambre des représentants des États-Unis. Il perd cependant la primaire républicaine face à Cynthia Lummis avec 37,4% des voix contre 46,2%[1]. En 2012, il est nommé trésorier du Wyoming par le gouverneur Matt Mead à la suite du décès en fonction de Joseph Meyer. Il est élu pour un mandat complet en 2014. À ce poste, il supervise notamment les investissements de l'État[1].
En , Gordon annonce sa candidature pour devenir le prochain gouverneur du Wyoming[1]. Il remporte la nomination républicaine avec 33% des voix, devançant notamment le donateur républicain Foster Friess soutenu par le président Donald Trump (25,3%)[2]. Dans un État qui compte quatre fois plus de républicains que de démocrates, il devient le favori de l'élection générale. Il est élu gouverneur en battant la démocrate Mary Throne par 67,1% des suffrages contre 27,5%[3].
Il est réélu en .
En 2023, le Wyoming devient le premier État américain à interdire la pilule abortive. Mark Gordon appelle ensuite les législateurs à aller plus loin et inscrire une interdiction totale de l’avortement dans la Constitution de l'État[4].