Rookie Lars Eller added an assist on the goal, earning his first career point with the Canadiens. After playing a solid game at both ends of the ice, Eller was rewarded with some overtime work.
Carey Price made 27 saves on the night to pick up his 5th win of the season.
The Canadiens move to 5-2-1and host the New York Islanders on Wednesday.
After a scoreless first period, that was a bit of a goaltending duel between Price and Ilya Bryzgalov, Kyle Turris was left alone out front to beat Price 5-hole at 2:49 of the second period.
Tomas Plekanec responded for Montreal 7:14 with his third goal of the season, on a play that had Bryzgalov looking lost and confused in his crease.
The Canadiens struggling power play, that missed on three opportunities in the first twenty minutes, finally connected just over two minutes later.
Roman Hamrlik fed Mike Cammalleri, who took advantage of using P.K. Subban as a decoy, to fire the shot past the Coyotes netminder for the Canadiens second power play marker of the season.
"We've been working on things on the power play, and it the puck hasn't been getting in with any regularity," Cammalleri said. "It's amazing what a goal will do for a team. It's almost like a shot of adrenaline."
The Habs are now 2-for-29 on the season, with the man advantage, and know there is more work to be done.
"Our power play is improving. We're creating more chances," said Canadiens coach Jacques Martin. "We're synchronizing a bit better, but we have areas where we have to improve."
The Coyotes power play unit has struggled itself, sitting 27th going into the night's action, but did manage to connect with the man advantage in the third period to tie it up. Derek Morris blasted a shot that may have deflected off the stick of Plekanec, and whisked past the head of a partially screened Price at 1:01.
Price continued to show the focus that eluded him last season, and for the latter part of 2008-09, by bouncing back to form immediatley after allowing a goal and shutting the door the rest of the way.
In overtime, Josh Gorges kept the play in the Phoenix end, shooting the puck towards the net. The shot deflected off the stick of Eller and right out to Kostisyn who snapped home the winner while tumbling into the boards in celebration.
"It's nice to be winning games early in the season." Cammalleri added. "He (Kostistyn) played well all game and it was good to see him win it."
PHX -(Wolski) - 2:49
MTL -(Kostitsyn, Cammalleri) 7:14
MTL -(PP) (Hamrlik, Subban) 9:23
PHX -(PP) (unassisted) 1:01
MTL - Andre Kostitsyn (Eller, Gorges) 1:25
Three Stars: 1. Andrei Kostitsyn 2. Mike Cammalleri 3. Tomas Plekanec
Sibling Rivalry: Tonight's game marked the second head-to-head meeting between brothers Tom Pyatt of the Canadiens, and the Coyotes Taylor Pyatt. Cousins Carey Price and Phoenix Captain Shane Doan did not get to meet up, due to the latter serving the final game of a three-game suspension.
Markov to return Saturday: The Canadiens went with the same winning lineup from over the weekend, but coach Jacques Martin did give word that Andrei Markov is expected to return to the lineup this Saturday, provided team doctors give him the OK.
A worthy cause: Alex Kovalev and goaltending legend Vladislav Tretiak are teaming up for charity.
Find out what the Coyotes are saying on the result at Five For Howling.