Kulemin was selected in the second round of the 2006 NHL Entry Draft by the Maple Leafs as a 44th overall pick. Kulemin was signed to a three-year contract by the Maple Leafs on May 25, 2007. However, Kulemin elected to stay with the Russian Super League for the 2007-08 season, as was agreed upon by the Maple Leafs and Kulemin's Russian club. Kulemin was the reigning Russian League MVP in 2007. Before the 2008-09 season, Kulemin was guaranteed a roster spot with the Maple Leafs, as the team was rebuilding, and hence was looking to inject a large quantity of youth into their roster.
During the 2008-09 NHL season, Kulemin has predominantly played on a scoring line with teammates Niklas Hagman and Mikhail Grabovski. The line has become one of, if not the most productive scoring line on the Maple Leafs. The line is well-regarded for its speed and skill, and the chemistry that exists between the three players. All three players are playing in their first season on the Maple Leafs. Kulemin scored his first NHL goal in his first NHL game against the Detroit Red Wings. The goal, which came off of Red Wings' goaltender Chris Osgood, turned out to be the game's game-winning goal, giving the Maple Leafs their first win of the season.