Kolesnik began his career with Kazzinc-Torpedo and spent five years with the club from Ust-Kamenogorsk before being signed as a free agent by the Colorado Avalanche on August 16, 2005.

He played for the Avalanche's minor league hockey team, the Lowell Lock Monsters, where he logged a 2.80 goals against average (GAA) and a .916 save percentage with a pair of shutouts.

On December 28, 2005, the Colorado Avalanche announced that Kolesnik was being sent back to Lowell, after starting seven NHL games, going 3–3–0, with a 3.29 goals against average and a .887 save percentage.

Earlier in the week, on December 21, it was announced that Kolesnik was selected to represent his home country of Kazakhstan in the 2006 Winter Olympics in Turin, Italy.

For the 2006–07 season, Kolesnik, with the ambition to become a starting goaltender, left North America to play for Khimik Mytishchi in the Russian Superleague (RSL).