May began his NHL career when he was drafted in the first round, 14th overall, by the Buffalo Sabres in the 1990 NHL Entry Draft. His possible greatest NHL achievement came during the 1993 Adams Division semi final playoff series against the Boston Bruins, where May scored the series-winning goal in the fourth game, which has been made famous due to its notable call by Buffalo broadcaster Rick Jeanneret.
On February 27, 2007, while with the Avalanche, May was traded to the Ducks for goaltender Michael Wall. This would prove to be a turning point of May's career, as the Ducks went on to win the Stanley Cup as NHL champion that season, and May had won his first championship in over 15 NHL seasons.
On January 7, 2009, May was re-united with former Ducks general manager Brian Burke, who, as new general manager of the Toronto Maple Leafs, acquired May in exchange for a conditional 6th round draft pick. The move was Burke's first as Toronto general manager, and was done to add the necessary physical play and veteran leadership that May provides.