Seit 1996 ist er Mitgliid vum Abgordnetehuus vu Berlin, syt 2001 as diräkt gwehlte Abgordete fir dr Wahlchrais Tempelhof-Schöneberg 4. Vu Juni 2001 bis Novämber 2011 isch er Vorsitzer vu dr SPD-Fraktion gsii, as Nofolger vum Klaus Wowereit no däm syre Wahl zum Regierede Burgermaischter am 16. Juni 2001. Noch em Ruggdritt vum Peter Strieder im April 2004 het er zuesätzli dr SPD-Landesvorsitz ibernuu. Am 9. Juni 2012 isch dr Müller in ere Champfabstimmig um s Amt vum Landesvorsitzer mit 101 Delegiertestimme gege dr SPD-Linke Jan Stöß unterläge, wu 123 Stimmen iberchuu het. Dr Müller het as änge Verdröute vum Klaus Wowereit gulte.