Growing up as a teenager in Slovakia, Demitra played 28 games for his hometown Spartak Dubnica of the Czechoslovakian second division in 1991-92 at the age of 17. After another four games with Spartak in 1992-93, Pavol joined Dukla Trencin of the Czechoslovakian Extraliga for 46 games. He also won a bronze medal with team Czech Republic at the 1993 World Junior Championships.

In 1993-94, Demitra travelled to North America and split the season between the NHL and the AHL's Prince Edward Island Senators. In 41 AHL games, he scored 41 points. Demitra began showing signs of tremendous offensive talent in 1995-96 when he scored 81 points in just 48 AHL games. In 1996, he represented Slovakia at the World Cup of Hockey.

Demitra made his NHL debut that year on October 9, 1996 with one assist in a 7-5 loss against the St. Louis Blues. Just five nights later, he scored his first NHL goal against the Florida Panthers. After playing only 12 games in 1993-94, Demitra suited up for 16 contests in the shortened 1994-95 season.

On November 27, 1996, Demitra was traded to the St. Louis Blues and in 1997-98, he joined the NHL ranks full time and scored 52 points in 61 games. In 1998-99, Demitra led the Blues with 37 goals and 52 assists for 89 points. He also participated in his first mid-season NHL All-Star Game and finished second in the NHL with ten game-winning goals.

In 1999-2000, Demitra led the Blues to a President's Trophy championship and played in the mid-season NHL All-Star Game. He finished the year with 75 points in 71 games and won the Lady Byng Trophy for his sportsmanlike play. In 2000-01, Demitra was limited to just 44 games, but still led the club with a +27 plus/minus rating. He had 20 goals and 45 points while the Blues reached the 100-point mark for the second straight year. Upon his arrival in St. Louis, Demitra proved to be one of the elite players in the NHL, surpassing the 500-games played and 500-point plateau during the 2003-04 season.

However, once the 2004-05 NHL lock out had been settled, Demitra soon after became a member of the Los Angeles Kings. His 25 goals helped lift the Kings offence but the team again failed to make the playoffs in 2005-06. Demitra was sent to the Minesota Wild for Patrick O'Sullivan and a 2006 first-round draft pick. As a member of the Wild, he teamed up with Marian Gaborik and recorded 64 points in 2006-07 and 54 points in 2007-08 and was a team Captain for the month of October in 2007.

In the summer of 2008, Demitra became an unrestricted free agent. After selecting Vancouver as his top choice, he signed a two-year $8 million contract with the club on July 10, 2008.

Aside from his World Junior appearance in 1993 and World Cup appearance in 1996, Demitra has represented Slovakia at the World Championships (1996, 2003-2005 and 2006), the 2002, 2006 Winter Olympics and the 2004 World Cup of Hockey.