Aleksandar Kolarov and Samir Nasri scored second half goals to consigned Everton to their first defeat of the 2015/16 season.
The Serbian struck a on the hour mark in a tightly-contested contest that, on another day, could have ended all square.
Both Phil Jagielka and Romelu Lukaku saw efforts graze the woodwork as the Blues went toe-to-toe with their table-topping opponenets.
Roberto Martinez kept faith with the side that defeated Southampton 3-0 at St Mary’s last time out, with Arouna Kone again deployed out wide on the flanks.
But it was City who carved out the opening chance. David Silva’s initial shot was blocked but the ricochet fell straight to Aguero but Tim Howard beat his effort away.
Howard was needed again minutes later, Navas swept the ball into the Argentine’s path from out wide but once more the American was equal to the City striker’s well-struck shot.
Silva was proving the Citizens’ orchestrator – he drove straight at Howard following Aguero’s lay-off, then very nearly teed up a lunging Raheen Sterling.
But it was Everton who had the ball in the net first – only for Lukaku to be ruled offside when collecting Barkley’s neat through ball.
The hosts went close again seconds later as Coleman powered forward from right-back, cut onto his left but dragged an effort narrowly off target. Sterling then saw Howard divert his own shot for a corner.
It was from an Everton set-piece though that the Blues came within a whisker of opening the scoring. Cleverley floated over a corner and Jagielka powered a header that brushed the top of the net as it went agonisingly over.
As the first half drew to a close, the Toffees were forced into an early change as Brendan Galloway limped off, with Tyias Browning slotting in at left-back.
There was also just enough time for Lukaku to fizz a free-kick that clipped the bar.
Supporters had barely returned to their seats after the break when Silva struck the woodwork after Sterling’s clever pass found him in space.
But on the hour, the visitors went in front. Sterling slipped the ball to the overlapping Kolarov, and the Serbian beat Howard with a low shot.
A mix up between Browning and Stones then let in Navas but with all the time in the world, the Spaniard shot straight at Howard.
Martinez replaced Kone with Steven Naismith seconds after the goal, with the Scot taking over one of the wide positions. Almost immediately Naismith found Barkley in space in the box but the youngsters effort was deflected over the bar.
Try as they might, Everton couldn’t find a way through a stubborn City rearguard. Twice a dangerous loose ball was hacked away desperately – the second off the line as Gareth Barry’s header looked like creeping over.
On came Gerard Deulofeu to inject pace and directness to the home side’s attack. Yet even the exciting Spaniard couldn't unlock a resolute City defence, and City made sure of the points as substitute Nasri added a late second to end Everton's early unbeaten start to the season.