The Premier League champions required a victory at home against the Spanish title-holders but things started poorly when Karim Benzema put the visitors ahead in the 10th minute.
City were given late hope when Sergio Aguero converted from the spot following a questionable penalty but it wasn't enough as Roberto Mancini's men failed to record maximum points to sit at the foot of the Group D table.
Borussia Dortmund went to the top of the group thanks to a 4-1 away win over Ajax whose progression chances were also extinguished. Robert Lewandowski netted a brace whilst Marco Reus and Mario Gotze were also among the goals.
In Group B, Arsenal moved through to the next phase courtesy of a 2-0 home win over Montpellier courtesy of second-half goals from Jack Wilshere and Lukas Podolski as Schalke also secured their path into the Round of 16 with a 1-0 victory over Olympiakos at home.
Group A saw Paris Saint-Germain ease past Dynamo Kiev with a 2-0 victory in Ukraine thanks to an Ezequiel Lavezzi double whiulst group leaders Porto saw off Dinamo Zagreb 3-0 to continue the Croatian side's run of no points in five matches in the competition.
2012/13 UEFA Champions League scores - Match Day 5
Dynamo Kiev (UKR): 0 Paris Saint-Germain (FRA): 2 (Ezequiel Lavezzi 45'/52') Olimpiysky National Stadium, Kiev, Ukraine - 36,712
Anderlecht (BEL): 1 (Tom de Sutter 79', red card: Bram Nuytinck 70') AC Milan (ITA): 3 (Stephan El Shaarawy 47', Philippe Mexes 72', Alexandre Pato 90') Constant Vanden Stock Stadium, Brussels, Belgium - 19,803