Following the 1994–95 lockout, the NHL entered a prolonged period of offensive decline. Throughout the 1980s, 7.6 goals were scored per game on average. That figure had dropped below six goals per game by the 1994–95 season, and to 5.19 by 1998–99. There have been many arguments put forth as to what caused this decline. A common claim is that the drop in offence was due to dilution of talent caused by 1990s expansion, a position former player Brett Hull endorsed. Increased use of the neutral zone trap and similar defensive systems were also blamed. The New Jersey Devils have often been criticized for popularizing the trap, using it to win the Stanley Cup in 1995, and again in 2000 and 2003. This period has been called the dead puck era.
The Canada Cup gave way to the World Cup of Hockey in 1996, an NHL-sanctioned eight team international tournament featuring the top professionals in the world. The inaugural tournament saw the United States upset the favoured Canadians in a three-game final. That same year, the Avalanche won their first Stanley Cup in their first season in Denver, sweeping the Florida Panthers. One year later, the Detroit Red Wings ended a 42-year drought, capturing their first Stanley Cup since 1955. The team's celebration was cut short, as forward Vladimir Konstantinov and team masseur Sergei Mnatsakanov were seriously injured when their limousine crashed six days following the victory. The Red Wings dedicated the 1997–98 season to the two. Upon repeating as champions in 1998, they brought Konstantinov, who had suffered severe brain damage in the crash, out in a wheelchair to celebrate with the team on the ice.
The NHL continued its expansion into the southern United States. In 1998, the Nashville Predators joined the league, followed by the Atlanta Thrashers in 1999. On April 16, 1999, Wayne Gretzky played his final NHL game, retiring as the league's all-time scoring leader and holding 61 NHL records. His number, 99, was retired league-wide the following season. The usual three year waiting period between a player's retirement and his induction into the Hockey Hall of Fame was waived, and he was inducted in 1999. In 2000, the league added its 29th and 30th franchises, the Minnesota Wild and Columbus Blue Jackets.
For marketing reasons, the NHL agreed to participate in the Winter Olympics starting in 1998. NHL players first competed at the Nagano Games. Led by goaltender Dominik Hasek, the tournament was won by the Czech Republic. Hasek, who finished the tournament with a 0.97 goals-against average and a .961 save percentage over six games, was the leading goaltender of the 1990s. His run of consecutive Vezina Trophies from 1994 to 1999 was interrupted only once, in 1996 by Jim Carey of the Washington Capitals. Hasek won another Vezina Trophy in 2001, and two consecutive Lester B. Pearson and Hart Trophies in 1997 and 1998.
The Panthers' trip to the Stanley Cup final in 1996 began a trend in which southern-based teams frequently appeared in the championship round. The Dallas Stars won the 1999 Stanley Cup over the Buffalo Sabres in controversial fashion: Brett Hull scored the Cup-winning goal in overtime of game six despite arguments that his foot was in the goal crease, which under the rules of the time would have disallowed the goal. The Stars returned to the finals in 2000, falling to the New Jersey Devils. The Hurricanes first played in the finals in 2002, losing to the Red Wings, while the Mighty Ducks reached the final in 2003, falling to the Devils. In 2004, the Tampa Bay Lightning defeated the Calgary Flames to win the Cup. The Lightning win in 2004 was seen as the end to the Devils/Avalanche/Red Wings Stanley Cup era, as the three teams won a combined 8 Stanley Cups between 1995 and 2003. The Dallas Stars in 1999 was the only team other than those three to win a Stanley Cup during that time.
The Edmonton Oilers hosted the NHL's first regular season outdoor hockey game, the Heritage Classic, on November 22, 2003. The game against the Canadiens was held at Commonwealth Stadium before a then-record crowd of 57,167 fans who endured temperatures as low as -19°C.