Erste Zusammenschlüsse (1957 bis 1958)

Bereits 1957 gründeten die beiden Eishockeyspieler Ted Lindsay von den Detroit Red Wings und Doug Harvey von den Canadiens de Montréal eine erste Spielerorganisation, nachdem die Liga sich geweigert hatte, Informationen zu möglichen Plänen für eine Altersversorgung der Akteure zu veröffentlichten. Die Arbeit der Organisation wurde allerdings durch die Clubbesitzer durch Spielertransfers oder der Verbannung zu Farmteams in den Minor Leagues behindert. Nach einer außergerichtlichen Einigung zu verschiedenen Themen wurde die Organisation schließlich aufgelöst.

Gründung (1967)

Die NHLPA in ihrer heutigen Form wurde schließlich im Juni 1967 von den Spielern der Original Six gegründet. Gründungsmitglieder und gleichzeitig Repräsentanten der Teams waren Eddie Johnston von den Boston Bruins, Pierre Pilote von den Chicago Black Hawks, Norm Ullman von den Detroit Red Wings, Bobby Rousseau und J. C. Tremblay von den Canadiens de Montréal, Rod Gilbert, Harry Howell und Bob Nevin von den New York Rangers sowie Bob Pulford von den Toronto Maple Leafs, der zugleich zum ersten Präsidenten der NHLPA ernannt wurde. Erster Geschäftsführer wurde der Promoter Alan Eagleson.

Erfolgreicher Vertrag zwischen NHL und NHLPA (1967 bis 1991)

Um ein Scheitern wie das des Vorgängers zu verhindern, einigten sich die Clubbesitzer und Pulford, der zuvor gedroht hatte, bei einer ausbleibenden Anerkennung durch die Vereine diese durch die unabhängige Behörde Canadian Labour Relations Board zu erreichen, auf ein Abkommen, das Spielern keine Sanktionen durch die Clubs bei Zugehörigkeit zur NHLPA garantierte. Im Gegenzug verpflichtete sich die Organisation, mindestens zwei Drittel der NHL-Spieler zu repräsentieren und nicht zu streiken, es sei denn, die Vereine verletzten eine der Vereinbarungen des NHL Collective Bargaining Agreement, kurz CBA.

Streiks und Lockouts (1991 bis 2005)

Alan Eagleson wurde im Jahr 1991 durch Bob Goodenow als Geschäftsführer abgelöst und wurde schließlich im Januar 1998 wegen Betruges während seiner Amtszeit zu einer Strafe von einer Million Kanadischer Dollar sowie 18 Monaten Gefängnis verurteilt. 1992 kam es erstmals zu einem Spielerstreik, in welchem die Akteure das Recht zur Vermarktung ihres eigenen Erscheinungsbilds forderten. In der Saison 1994/95 kam es erneut zu einem 104-tägigen Lockout, der Aussperrung der Spieler durch die Vereine, nachdem sich die Teameigner und die Spielergewerkschaft nicht über die Erneuerung des NHL Collective Bargaining Agreement hatten einigen können. Als schließlich eine Einigung getroffen werden konnte, waren bereits 38 Spieltage dem Streik zum Opfer gefallen, sodass die Regular Season in nur 48 statt 84 Spieltagen ausgetragen wurde.

Im Sommer 2004 fanden erneut Verhandlungen statt, bei denen jedoch wiederholt keine Einigung erzielt werden konnte. So kam es erneut zu einem Lockout. Am 16. Februar 2005 gab NHL-Chef Gary Bettman die komplette Saisonabsage bekannt, weil auch weitere Treffen zu keinem Ergebnis führten. Erst am 13. Juli 2005 einigten sich Clubbesitzer und Gewerkschaft auf die neuen Eckpunkte des CBA, welche am 22. Juli 2005 ratifiziert wurden und damit der 310 Tage dauernden Streik ein Ende fand. Das neue Vertragswerk mit der NHLPA hat eine Laufzeit von sechs Jahren und endet zum 15. September 2011, wobei die NHLPA die Option besitzt, dieses einseitig um ein weiteres Jahr zu verlängern.

Spionageaffäre und Konsolidierung (seit 2005)

Knapp eine Woche nach dem offiziellen Ende des Arbeitskampfes trat nach 15 Jahren an der Spitze der Spielervertretung Präsident Robert W. Goodenow von seinem Amt zurück. Sein Nachfolger wurde Ted Saskin, der im Arbeitskampf Verhandlungsführer der Spielergewerkschaft war. Dieser wurde im Mai 2007 seines Amtes nach einer Spionageaffäre um die E-Mail-Konten verschiedener NHL-Spieler enthoben. Daraufhin wurden die Spieler Michael Cammalleri von den Los Angeles Kings, Robyn Regehr von den Calgary Flames, Chris Chelios von den Detroit Red Wings, Shawn Horcoff von den Edmonton Oilers sowie der Free Agent Eric Lindros mit der Bildung eines Komitees zur Suche eines neuen Geschäftsführer beauftragt. Am 24. Oktober wurde der Bostoner Anwalt Paul Kelly als Nachfolger Saskins vorgestellt. Seine Amtszeit währte allerdings keine zwei Jahre, da er am 31. August 2009 entlassen und auf Interimsbasis zunächst durch Ian Penny und später durch Mike Ouellet ersetzt wurde. Seit dem 18. Dezember 2010 führt Donald Fehr die Geschäfte der Gewerkschaft.