The duo scored to grab three points in dramatic style after Rickie Lambert and Steven Davis had emerged from the substitutes' bench to cancel out Carlos Tevez's opening goal
The excellent Carlos Tevez gave City a first half lead, although Roberto Mancini had been dealt an early blow when Sergio Aguero left the game on a stretcher with a knee injury.
Southampton had been largely confined to its own half before it stunned the hosts by racing into a 2-1 lead in the second half courtesy of goals from substitutes Rickie Lambert and Steven Davis.
But Edin Dzeko quickly grabbed an equalizer and Samir Nasri, the architect of much of City's best play, completed the comeback with 10 minutes to play.
Mancini handed new signing Jack Rodwell his City debut in central midfield, where he partnered Yaya Toure in the absence of the injured Gareth Barry, while Joe Hart was passed fit to start in goal.
17-year-old midfielder James Ward-Prowse made his first ever league appearance in midfield for the Saints, with last season's Championship top scorer Lambert left on the bench as Guly do Prado started in attack.
Having written his name into the history books at the end of last season, Aguero started the new campaign with a moment that he will hope will not last so long in his memory. The Argentine forward appeared to twist his knee under the sliding challenge of right-back Nathaniel Clyne – who cleanly won the ball – and, after one attempt to get back to his feet, left the interior of the Etihad Stadium on a stretcher.
Almost unnoticed amidst the worries of Aguero, Southampton had settled into the game nicely, with Ward-Prowse rushing forward with confidence from central midfield and Joleon Lescott under scrutiny for a tackle on Rodriguez in the City box.
The Saints were soon to discover, however, the Premier League champions' ability to turn a game in the blink of an eye. After Dzeko had replaced Aguero, Nasri flicked David Silva's pass into the path of Tevez, who spun past center back Jos Hooiveld into the box and was tripped by the Dutch defender's outstretched leg, leaving Howard Webb no choice but to point to the spot.
With Aguero withdrawn and other regular takers Mario Balotelli and James Milner on the bench, Silva had the chance to send City in front but his penalty was as poorly struck as Shane Long's for West Brom against Liverpool the day before and Kelvin Davis saved to his left.
Southampton found breaks forward more difficult to come by as the half wore on but defended resolutely, keeping Dzeko away from crosses aimed by fullbacks Pablo Zabaleta and Gael Clichy. Kelvin Davis saved comfortably when Tevez, who carried his impressive preseason form into this fixture, engineered enough space to toe-poke an effort from 18 yards towards goal.
He was not kept at bay for much longer. Southampton were five minutes away from reaching the break with the deadlock intact when Nasri, allowed too much time and space in the visitors' half, picked out Tevez with a chipped pass that the Argentine scurried on to – just staying in line with Jose Fonte – and rifled past Kelvin Davis at the near post.
From that point Nigel Adkins' team desperately defended to keep the deficit to one-goal until halftime. Tevez's drilled effort was saved by Kelvin Davis, who could not quite keep his hands on the ball but saw Silva's attempted follow-up blocked.
Southampton did make it to the break trailing by only a goal but the game was almost put to bed shortly after the restart. Nasri, perhaps only second to Tevez in influence exerted in the first half, fought off Clyne on the left-hand side before directing a low cross into the path of Dzeko, but the Bosnian failed to get proper contact on the ball from point blank range.
Clichy came even closer to goal minutes later when he latched on to Toure's superb pass to the back post, but the left-back sent a first-time volley over the crossbar.
Adkins had seen enough, calling Lambert to the touchline in one of two moves that would turn the game on its head, but the striker was still waiting to replace Rodriguez when Silva passed up another golden opportunity. Tevez sped down the right and forced Kelvin Davis to parry his powerful cross before the Spaniard volleyed on to the crossbar after Nasri had controlled the rebound.
It took Lambert less time to find his range and make his mark on the top flight. Guiding a Southampton attack forward, the 30-year-old superbly steered home a precise shot from the edge of the box after Lescott had blocked his attempted through ball back into his path.
The Saints' second half possession had hovered around the 20 percent mark and from that point it seemed that preserving their point at all costs would be the order of the day but, once again, Adkins found a way to inspire his team from the bench.
Steven Davis was brought into the fray this time and when Rodwell's poor pass sparked a counterattack, the former Rangers midfielder took advantage of Adam Lallana's lay-off to find the bottom corner with another fine finish.
The story, with City trailing 2-1, seemed a familiar one and it was to take a familiar next step. This time, it did not take as long for the man who gave the fans inside the Etihad Stadium back in May a shred of hope to find an equalizer. Vincent Kompany returned Nasri's corner to the penalty area with a low shot and after Toure had scrapped for the ball it fell for Dzeko to slam home.
Substitute Balotelli missed failed to convert a sublime low cross from Nasri as City searched for another dramatic third goal before Dzeko glanced a header narrowly wide.
Once Dzeko had equalized a winner seemed almost inevitable and City found it with 10 minutes still to play. Clichy's cross from the left was poorly dealt with by his opposite number Danny Fox, with Nasri making no mistake after the defender had headed the ball directly into his path.
Fonte had one chance to grab a point as Southampton pressed for a late leveler but City held out to register its first points of the new campaign.
Follow GOAL.COM USA on