In december 1919 trad Müller in dienst van het hoofdbureau van politie in München. In 1929 werd hij benoemd tot Polizeisekretar en in 1933 tot Kriminalinspektor. Een groot deel van zijn politiecarrière hield hij zich bezig met het vergaren van informatie rond de Duitse communistische partij (KPD). Müller stond bekend als een anti-communist en tijdens zijn politiewerk scheen hij zich regelmatig niet gebonden te voelen aan de wet. Zijn lak aan de wet vormde in de toekomst geen enkel probleem. Vanaf het moment dat Hitler aan de macht kwam werden er allerlei maatregelen genomen die er voor zorgden dat politie- en veiligheidsfunctionarissen in hun werk niet gebonden waren aan wetten die hun arrestanten zouden beschermen.
Müller stond bij de nazi’s al gauw bekend als een professionele politiefunctionaris en zijn fanatieke toewijding aan plicht en efficiency vielen ook bij Heinrich Himmler op. In 1935 werd Müller benoemd tot opzichter van de Kriminalpolizei (recherche). Intussen was Müller in april 1934 in dienst getreden van de Schutzstaffel (SS) in de rang van SS-Untersturmführer en op 4 juni 1934 werd hij benoemd tot SS-Obersturmführer. Tevens kreeg hij een positie binnen de Sicherheitsdienst (SD), de inlichtingendienst van de SS. De aanzet tot een prominente carrière binnen het Derde Rijk was hiermee in gang gezet.
Toen Heydrich in april 1934 door Himmler werd benoemd tot chef van de Gestapo (Geheime Staatspolizei) benoemde hij Müller tot hoofd van afdeling II. Deze afdeling was verantwoordelijk voor het opsporen van mogelijke vijanden van het Derde Rijk, waaronder Joden. Binnen de SS werd hij op 30 januari 1937 benoemd tot SS-Standartenführer en in de maand juni van datzelfde jaar werd hij naast afdelingshoofd van de Gestapo benoemd tot bestuursadviseur van de Kriminalpolizei. Binnen het politieapparaat nam Müller hiermee een steeds belangrijker functie in. In 1938 werd Müller voor het eerst direct betrokken bij een belangrijke gebeurtenis uit de geschiedenis, de Reichskristallnacht.
Vanuit het hoofdkantoor van de Gestapo op de Prinz Albrecht Straße 8 in Berlijn stuurde Heinrich Müller per telex op 9 november 1938 een dringende geheime boodschap aan alle politiebureaus in het Derde Rijk. Müller schreef: "Binnenkort zullen er in het Reich acties tegen Joden en in het bijzonder tegen synagogen plaatsvinden. Die mogen niet tegengewerkt worden. Er moet evenwel contact worden opgenomen met de Ordnungspolizei zodat plunderingen en excessen worden voorkomen". Hij vervolgde: "Er dienen voorbereidingen te worden getroffen voor de aanhouding van 20 tot 30 duizend Joden in het hele Reich. Vooral de welvarenden moeten worden opgepakt. Gedetailleerde aanwijzingen volgen in de loop van de nacht." Deze nadere instructies kwamen van Heydrich en werden om 01.20 uur per telex naar de Gestapo en SD-bureaus verzonden. Heydrich’s orders bevestigden de boodschap van Müller, maar Heydrich gaf in zijn bericht iets meer details. Ontvangst van Heydrichs bericht moest worden gemeld bij Müller. Ondanks de pogingen van Heydrich en Müller om de pogrom te coördineren liep de Reichskristallnacht uit op een ongeorganiseerde chaos. De Sturmabteilung (SA) had de boodschap niet begrepen en 7500 winkels, 29 warenhuizen en 171 huizen werden verwoest; 191 synagogen brandden volledig af en nog eens 76 werden anderszins verwoest; elf Joodse gemeenschapscentra, dodenkapellen en vergelijkbare gebouwen werden in brand gestoken en nog eens drie werden geplunderd. Mede in opdracht van Müller werden minstens 30.000 Joodse mannen gearresteerd en opgesloten in concentratiekampen.
Het eerste in scène gezette incident was een "Poolse aanval" op een radiostation nabij Gleiwitz aan de Pools-Duitse grens. Duitse SD-ers verkleed als Polen moesten het radiostation aanvallen en door de zender in het Pools aankondigen dat de strijd tussen Duitsland en Polen was aangebroken. Het tweede in scène gezette incident was een "aanval" op de Duitse douanepost Hochlinden. Een groep Poolssprekende Duitse manschappen voorzien van Poolse uniformen en wapens zou de douanepost overvallen en vervolgens een schijngevecht leveren met SS troepen. Om de buitenlandse pers te overtuigen en als materiaal voor het Duitse propaganda-apparaat had Heydrich praktisch bewijs nodig en daarbij kon Müller hem van dienst zijn.
Het praktische bewijs bestond uit de stoffelijke overschotten van de zogenaamde Poolse aanvallers. Müller leverde meer dan tien veroordeelde gevangenen uit de concentratiekampen, die een dodelijke injectie toegebracht kregen en werden achtergelaten op de plaatsen waar de aanvallen in scène gezet waren. Om alles overtuigend te maken werden de lichamen in Poolse uniformen gestoken en zouden zij zelfs Poolse legerpasjes op zak hebben. Na afloop van de in scène gezette operaties werd de pers uitgenodigd zodat zij getuige konden zijn van de "Poolse aanval". Heydrich was na afloop erg trots op zijn eigen plan en ook zijn superieuren waardeerden zijn organisatorische talent. Toen op 27 september het Reichssicherheitshauptamt werd opgericht, werd hij benoemd tot chef van deze organisatie. Ook voor Müller was er een belangrijke rol weggelegd binnen het RSHA.
Op 24 januari 1939 gaf Hermann Göring (verantwoordelijk voor de supervisie over en de coördinatie van het gehele anti-Joodse beleid) Heydrich de opdracht voor de ontwikkeling van het Centraal Rijksbureau voor Joodse emigratie (Zentralstelle für Jüdische Auswanderung). Heinrich Müller kreeg leiding over dit bureau en hij pakte zijn taak fanatiek aan. Müller zorgde ervoor dat afgevaardigden van Joodse gezinnen per dag een lijst moesten inleveren van zeventig Joodse gezinnen die zich op hun emigratie moesten voorbereiden. Tegen het einde van 1939 zouden op deze wijze 78 duizend Duitse en Oostenrijkse Joden en 38 duizend Tsjechische Joden het Derde Rijk verlaten. Deze verplichte emigratie vormde echter geen bevredigende oplossing van het probleem en uiteindelijk zouden vele Europese Joden vernietigd worden in de gaskamers van onder andere Auschwitz-Birkenau, Sobibor en Majdanek. Voor het echter zover was werden eerst zogenaamde Einsatzgruppen geformeerd. Dit waren mobiele doodseskaders die in de Sovjet-Unie, tijdens operatie Barbarossa, achter de optrekkende Duitse troepen Joden moesten vermoorden.
Müller was inmiddels op 16 december 1940 benoemd tot Generalmajor der Polizei en werd op 29 november 1941 benoemd tot SS-Gruppenführer en Generalleutnant der Polizei. In april 1941 was Müller aanwezig bij een vergadering met Heydrich waarin de formatie van de Einsatzgruppen centraal stond. Heydrich sprak van een ‘harde opdracht’ die inhield dat ‘in veroverde gebieden in Rusland veiligheid en rust moesten worden gewaarborgd’. Deze woorden verbloemden de concrete taak van de Einsatzgruppen, maar alle aanwezigen begrepen dat het Heydrich ging om het vermoorden van Joden. Slechts één van de aanwezigen wilde vrijwillig meewerken, dit was Heinrich Müller.
De rol van Müller binnen de organisatiestructuur van de Einsatzgruppen was weer achter de schermen. Müller gaf mede in opdracht van Heydrich commando’s door aan de commandanten van de vier Einsatzgruppen. Zo gaf hij op 1 augustus het geheime bevel aan deze commandanten om alle activiteiten van hun eenheden in het oosten te melden. Hitler kon op deze wijze op de hoogte gehouden worden van hun progressie. Ondanks dat de activiteiten van de Einsatzgruppen geheim waren, was het toch de bedoeling dat al hun misdaden geregistreerd werden. In 1942 gaf Müller het bevel om alle bewijzen van massamoord in Oost Europa door de mobiele doodseskaders te vernietigen. Tijdens de Wannseeconferentie waren de nazi’s het eens geworden over een "definitieve oplossing van het Joodse vraagstuk". De Einsatzgruppen bleken niet efficiënt genoeg en het uitroeien van het Europese Jodendom werd vanaf dat moment efficiënter aangepakt.
Tijdens de Wannseeconferentie op 20 januari 1942 vertegenwoordigde Müller de Gestapo. Op de vergadering werd de organisatie van de vernietiging van Joden in de vernietigingskampen besproken. Na afloop van de vergadering, toen de meeste genodigden inmiddels vertrokken waren, hadden Müller, Eichmann en Heydrich een gezellig onderonsje. Terwijl ze zojuist plannen hadden gemaakt om het Joodse volk in Europa volledig uit te roeien, ontstond er bij de kachel onder het genot van een glaasje cognac een ontspannen sfeer. De drie bureaumoordenaars schenen totaal geen moeite te hebben met de vreselijke plannen die ze zojuist beraamd hadden. Gezamenlijk waren ze, naast hun chef Heinrich Himmler, de belangrijkste organisatoren van de holocaust.
Op 27 mei 1942 werd er door Tsjechische verzetsstrijders een moordaanslag op Heydrich gepleegd. Op 4 juni overleed hij in het ziekenhuis aan de gevolgen van deze aanslag. Heinrich Himmler nam zijn functie als chef van het RSHA tijdelijk waar maar er moest gezocht worden naar een waardige opvolger. Müller had een zeer geschikte en logische opvolger van Heydrich geweest kunnen zijn, maar toch werd hij gepasseerd. Op 31 januari 1943 werd Ernst Kaltenbrunner benoemd tot het nieuwe hoofd van het RSHA. Voordat hij chef van RSHA werd, was deze onder andere staatssecretaris van openbare veiligheid in Oostenrijk en had hij in deze functie toezicht op de Zentralstelle für Jüdische Auswanderung van Eichmann. Kaltenbrunner bleef tot 8 mei 1945 het hoofd van het RSHA. Müller was vermoedelijk voor deze functie gepasseerd omdat hij anders in de ogen van Himmler teveel persoonlijke macht kreeg.
Tot de laatste dag van Hitler’s leven was Müller trouw aan zijn Führer. De laatste plaats waar Müller gezien werd was in de Führerbunker, een dag na de zelfmoord van Hitler. Vanaf dat moment is het onbekend wat er gebeurd is met Müller. Geruchten gaan dat hij ondergedoken zou zijn onder de schuilnaam luitenant Schmidt in Altaussee in Oostenrijk en dat hij vervolgens in verschillende Amerikaans interneringskamp gevangen gezeten heeft. Mogelijk werkte Müller na de oorlog ook voor de Amerikaanse inlichtingendienst, de CIA. Concrete bronnen die kunnen aantonen wat er na de oorlog met Müller gebeurde, zijn er echter niet en feiten over het naoorlogse leven van Müller zijn dan ook niet bekend. Zeker is dat Müller, die een grote invloed gehad heeft op de terreur van het nazipolitieapparaat en de organisatie van de holocaust, niet berecht is voor zijn misdaden. Daarnaast is de persoon Müller in de geschiedenisboeken enigszins op de achtergrond gebleven. Mogelijk doordat Müller vooral op de achtergrond werkte, is er in de geschiedschrijving meer aandacht besteed aan de mensen die met hun werkzaamheden op de voorgrond traden. Met name Heinrich Himmler, Reinhard Heydrich en Adolf Eichmann staan bekend als Hitler’s moordenaars, Müller mag aan dit illustere rijtje echter niet ontbreken. Hij werkte regelmatig direct samen met Heydrich, was de baas van Eichmann en daarnaast was hij als leider van de Gestapo verantwoordelijk voor de terreur die deze organisatie zaaide in nazi-Duitsland en bezet Europa.