City went ahead through Emmanuel Adebayor's penalty and dominated the early part of the match.
But Wolves equalised through Nenad Milijas and then Edwards earned Mick McCarthy's side their first victory since the opening day of the campaign.
City started the game as if they were going to win at a canter as they threatened to prise open the Wolves defence every time they ventured forward.
But after going ahead they seemed content to sit back, which allowed Wolves back into the game - and they seized the opportunity.
Matt Jarvis enhanced his England credentials with another sparkling performance on the flank as he supplied a string of menacing crosses.
With Stephen Hunt finally fit to make his league debut on the opposite wing, there was a far better balance about the home side.
It was only in the final quarter of the game, with the introduction of Adam Johnson, that City regained their early momentum.
Mario Balotelli had the chance to break the deadlock when he got on the end of a low cross from James Milner but he could only stab the ball wide under pressure from Kevin Foley.
Vincent Kompany got on the end of a David Silva corner and his glancing header was cleared by Milijas although it may have been drifting just wide.
After 23 minutes Adebayor scored his first Premier League goal of the season from the penalty spot to put City ahead.
Jerome Boateng played the ball through to Silva and he was brought down close by Stearman.
Referee Mike Dean pointed to the spot and Adebayor sent Marcus Hahnemann the wrong way.
Wolves responded in a positive fashion and David Edwards twice went close to equalising in the space of a minute.
City's England goalkeeper Joe Hart did well to fingertip behind a header from the Wolves midfielder after he got on the end of a cross from Jarvis.
But Hart was relieved to see a thumping header from Edwards hit the post from another dangerous ball into the box from the impressive Jarvis.
The home side were not to be denied and after 29 minutes Milijas brought them back on level terms.
A cross from Jarvis was blocked but the ball broke into the path of Milijas who beat Hart with his low drive into the corner.
Wolves were suddenly in the ascendancy and Jarvis supplied another telling cross which only just eluded the run of Hunt at the far post.
But they had a let-off after 41 minutes when Adebayor outjumped Hahnemann and glanced his header inches wide from Balotelli's cross.
There was a quiet start to the second half but after 56 minutes Edwards put Wolves in front.
Doyle had his shot blocked by Kolo Toure from Foley's cross but the rebound fell to Edwards who kept his cool before sliding the ball past Hart and into the right corner.
Hunt was yellow-carded two minutes later when he tugged at the shirt of Adebayor as the striker tried to break clear down the left.
City tried to retaliate and Hahnemann did well to tip a low shot from Silva around the post after he had been teed up by Milner.
But Wolves were looking full of confidence and Hart had to be alert to get his body behind a low 30-yard attempt from Milijas.
Adebayor missed a great chance to level after 74 minutes, shooting over the bar after Johnson drilled the ball across the box.
It was Adebayor's last contribution before he was replaced three minutes later by full-back Pablo Zabaleta.
Zabaleta and Balotelli were booked in the closing stages as Wolves held on for a valuable win.