Paul Messier is one of the few NHL players with the distinction of having been born in England. He and his family moved to Canada when he was young and he grew up playing hockey in the Edmonton minor system. At 15 Messier played for the Edmonton Mets of the AJHL, scoring 37 goals and 76 points in 59 games. The next year he played for the Spruce Grove Mets in the same league, collecting 45 goals and 101 points in 57 games. He was also called up to play one game with the Edmonton Oil Kings of the WJHL.
In 1975-76 he spent most of his season with Spruce Grove but was called up to play eleven games with the Oil Kings where he had a goal and 12 points. At 18, he decided to enroll at the University of Denver where he played for two years. After posting a 51-point season on 20 goals and 31 assists in 1977-78, Messier was selected by the Colorado Rockies with the 41st pick in the 1978 NHL Amateur Draft.
Messier played his entire nine-games in the NHL with the Rockies in 1978-79, failing to register a point. He also played with the Philadelphia Firebirds of the AHL and the Tulsa Oilers that year. He continued to play exclusively in the minors for another four years with the Fort Worth Texans, Birmingham Bulls and Wichita Wind of the CHL and the Binghamton Whalers and Moncton Alpines of the AHL.
In 1983-84 Messier decided to move to Germany where he played for six years, one with Iserlohn ECD and five with Mannheim ERC. He then played two games with Bolzano HC of the Italian League in 1990-91 before retiring.