Martin termine ses études secondaires au Argyle High School en 1974. Il travaille comme compagnon charpentier pendant plusieurs années, et il travaille dans les industries forestières, minières et de construction. Martin sert également à titre de gérant d'affaires du Syndicat des charpentiers du Manitoba de 1989 à 1997, et il est vice-président de la Fédération des travailleurs du Manitoba pendant un certain temps.
Martin est d'abord élu à la Chambre des communes du Canada lors de l'élection générale fédérale de 1997, défaisant le député libéral sortant David Walker(en) par une marge de 10 979 votes contre 9 895. Sa circonscription de Winnipeg-Centre, auparavant connue sous le nom de Winnipeg-Centre-Nord, avait successivement été représentée de 1921 à 1984 par J.S. Woodworth et Stanley Knowles, deux des plus importants politiciens social-démocrates dans l'histoire canadienne. La victoire de Martin sur Walker retourne la circonscription au NPD pour la première fois depuis 1988.
Martin défend les droits des travailleurs et des autochtones canadiens, et dénonce les vides législatifs permettant l'évasion fiscale des entreprises. Il a appuyé la candidature de Bill Blaikie à la direction du NPD en 2002-2003.
Il a réclamé la démission de Svend Robinson du dossier des affaires étrangères du NPD en 2002 après la visite de Robinson à l'Autorité palestinienne.
