Heinrich Müller, aki a náci rendszer szinte összes háborús és emberiség elleni bűntettében részt vett, a weimari köztársaság idején a bajor államrendőrség állományában szolgált nyomozóként. Walter Schellenberg SS-Oberführer, a náci katonai hírszerzés főnöke és a „Reichsführer-SS", Heinrich Himmler bizalmasának visszaemlékezése szerint az 1920-as években Müller erősen szimpatizált a marxista eszmékkel és a kommunista mozgalommal.
A bajor államrendőrség kötelékébe belépve azonban ez sem akadályozta meg abban, hogy részt vegyen a kommunista szervezetek elleni akciókban, bár az is igaz, hogy Heinrich Müller rendőrnyomozóként az ekkor még éppen csak feltörekvő nácikkal sem bánt éppen kesztyűs kézzel.
Adolf Hitler és a Nemzetiszocialista Német Munkáspárt (NSDAP) 1933-ban történt hatalomra jutása után a politikai és a bűnügyi rendőrség összevonásával létrehozott Biztonsági Rendőrségi Főhivatal (Hauptamt Sicherheitspolizei ) kötelékébe került, Reinhard Heydrich beosztottjaként.
Többek szerint Heinrich Müller nem volt az az árja felsőbbrendűségben valamint az antiszemita fajelméletben vakon hívő náci, mint amilyen a főnöke, Heydrich, illetve annak a közvetlen környezete, hanem sokkal inkább
a náci elnyomó apparátus vaskalapos, munkamániás és mindenféle empátiától mentes kíméletlen bürokratája, méghozzá ennek a legrosszabb fajtájából.
Müller 1934-ben belépett az SS-be, viszont a pártfelvételi kérelmét többszöri is visszadobták. Az egykori müncheni nácik közül ugyanis szép számmal akadtak olyan befolyásossá lett pártfunkcionáriusok, akik még jól emlékeztek arra, hogy Müller a bajor államrendőrség nyomozójaként hogyan viselkedett a „kamerádokkal".
Müllert így végül csak 1939-ben vették fel a Nemzetiszocialista Német Munkáspártba. Ugyanebben az évben hozták létre az összes náci elnyomó apparátust egyesítő csúcsszervet, a Birodalmi Biztonsági Főhivatalt (Reichssicherheitshauptamt, RSHA ), amelynek az ekkor már SS-rendőrtábornoki rangban álló Reinhard Heydrich lett a teljhatalmú vezetője. A fanatikus és kegyetlen Heydrich Obergruppenführertől
még a náci hierechia csúcsán álló főemeberek is tartottak.
Heydrich 1939. október elsejei hatállyal régi és megbízható beosztottját, Heinrich Müllert nevezte ki az RSHA VI. osztály, vagyis a Gestapo élére.
Müller nem is okozott csalódást Heydrichnek, aki a vezetősége alatt a Gestapót a náci elnyomóaparátus legrettegettebb szervezetévé építette ki. A Gestapo vezetőjeként részt vett a hivatalába integrált hírhedt IV B. alosztály, az úgynevezett „zsidóügyi csoport" létrehozásában, amelynek az élére a hozzá hasonlóan kíméletlen Adolf Eichmann SS-Sturmbannführert nevezte ki. A Gestapo, vagyis a politikai rendőrség a besúgói révén egész Németországot és a nácik által megszállt országokat is behálózta.
Müller alatt olyan kínzási módszereket rendszeresítettek a Gestapónál, amelyek kegyetlensége még a legbetegebb emberi fantáziát is meghaladta. "Mi még az egyiptomi múmiákat is szóra bírjuk" – ecsetelte a módszereik „hatékonyságát" az ekkor már csak Gestapós Müllerként emlegetett rettegett náci vezető. Müller és Eichmann is részt vett a főnökük, Heydrich által 1942 január 30-ára összehívott titkos tanácskozáson, a wannsee-i konferencián, amelyen elhatározták az európai zsidóság tervszerű kiirtását.
Reinhard Heydrich parancsára Müller állította össze a megszállt keleti területeken ténykedő SS kivégző alakulatok, az Einsatzgruppék számára készített likvidálási utasításokat, és ugyancsak tevékenyen részt vett az alárendeltségébe tartozó „zsidóügyi osztály" irányításában, vagyis az európai zsidóság deportálásában és meggyilkolásában.
Noha a megsemmisítő táborok felügyelete nem a Gestapóhoz tartozott, de Müller az összes nagyobb koncentrációs táborban, így az Auschwitz- Birkenau-i halálgyárba is Gestapo-kirendeltségeket telepített.
A megszállt országokban a Gestapo kiméletlen hajszát folytatott az ellenállási mozgalmak tagjaival és bárki mással szemben is, akiről azt feltételezték, hogy a Harmadik Birodalom ellensége.
Heinrich Müller kezéhez megszámlálhatatlanul sok ártatlan ember vére tapadt,
ezért sem vételen, hogy őt tartották a náci Németország legnagyobb „iróasztali gyilkosának". Amikor 1943.november végén a szövetséges nagyhatalmak Teheránban megtartott konferenciáján döntés született a háborús bűnösök felkutatásáról és megbüntetéséről, Heinrich Müller is felkerült a legkeresettebb náci bűnözők listájára.
A bukás végnapjaiban, 1945 áprilisának végén a náci főemeberek tömegesen igyekeztek elhagyni a szovjet ostromgyűrűbe fogott birodalmi fővárost, Berlint. Április 20-án, Adolf Hitler 56. születésnapján utoljára gyűltek össze a legfőbb náci párt és állami vezetők a rommá lőtt birodalmi kancellária egyik épségben maradt termében, hogy a Führernek tett születésnapi jókívánságaik után sietősen elhagyják a szovjet nehéztüzérség hatósugarába került veszélyessé vált birodalmi fővárost.
Csak Joseph Goebbels propagandaminiszter és Martin Bormann pártkancellár tartottak ki Hitler mellett, hogy a kancellária bunkerének földalatti betonszarkofágjába bezárkózva osztozzanak a sorsában.
Heinrich Müllert is ezekben a napokban látták utoljára Berlinben,
aki pár nappal Hitler április 30-án elkövetett öngyilkossága előtt rövid látogatást tett a „Führer-bunkerben". Hogy mi történt eztután Müllerrel, arra mind a mai napig nincs semmilyen biztos támpont.
A szövetségesek körözési listájának élén szereplő Müllert más prominens nácikkal szemben nem sikerült elfogni, és arra sem találtak kétséget kizáró bizonyítékot, hogy meghalt volna a berlini ostromban;
1945 májusában egyszerűen nyoma veszett a „Gestapós Müllernek".
Egy beszámoló szerint 1945 áprilisának legvégén sikerült kiszöknie Berlinből, és álnéven eljutnia a semleges Svájcba, ahonnan Dél-Amerikába távozott.
Amikor az izraeli titkosszolgálat három ügynökének 1960 májusában sikerült az álnéven Argentínában bujkáló Adolf Eichmann nyomára bukkania, elfogni, majd kalandrgénybe illő módon Izraelbe vinnie a régóta keresett náci háborús főbűnöst, az izraeli nyomozó hatóságok Eichmannt Müller sorsáról is kikérdezték. Eichmann azonban semmit sem tudott arról, hogy Müller Dél-Amerikába szökött volna.
A Moszad ügynökei Müller egykori titkárnőjét és szeretőjét is megfigyelték illetve kikérdezték, de ez a nyom sem vezetett eredményre. Walter Schellenberg, aki az SD, illetve Canaris tengernagy leváltása után az Abwehr, vagyis a külföldi hírszerzés főnöke volt, a háború után azt állította, hogy Müller már 1945 előtt konspiratív módon dolgozott a Szovjetuniónak, amolyan kettős ügynökként. Schellenberg, amikor az amerikai titkosszolgálat, az OSS kihallgatta Müller sorsával kapcsolatban, azt sejttette , hogy a „kommunista szimpatizáns" egykori Gestapo-főnök szovjet zsoldba állt, mert az NKVD azt remélte, hogy Müller „szakértelméből" a szovjet titkosrendőrség is sokat profitálhat.
A nürnbergi perben felelősségre vont Ernst Kaltenbrunner, aki Heydrich halála után az RSHA első számú vezetője, és így Müller főnöke lett, valószínűtlennek tartotta Schellenberg vélelmét. De azt, hogy Müller titokban az NKVD szolgálatába állt volna, korábbi beosztottja, Heinz Pannwitz is tagadta. Panwitz 1945 után szovjet fogságba került, és szabadulása után azt nyilatkozta a CIA ügynökeinek, a Szovjetunióban eltöltött évek arról győzték meg, hogy Heinrich Müller nagy valószínűséggel már 1945 májusában meghalt.
1963 szeptemberében feltárták azt a berlini Lilienthal utcai temetőben lévő sírt, amely állítólag Müller holttestét rejtette. A szakértői vizsgálat azonban bebizonyította, hogy a sírban fellelt maradványok nem lehetnek Mülleréi. Johannes Tuchel professzor, a Német Ellenállás Emlékhelye alapítványi vezetője saját kutatásaira hivatkozva 2013-ban bejelentette, hogy Heinrich Müller 1945 májusában meghalt – vagy a Berlinből való szökése közben érte halálos lövés, vagy pedig Martin Bormannhoz hasonlóan öngyilkos lett –,
a holttestét pedig a Mitte negyedben lévő zsidó temetőben ásott tömegsírba földelték el.
A Németországi Zsidók Központi Tanácsának elnökét valósággal sokkolta Tuchel professzor bejelentése, de a vélelmezett tömegsír feltárására még sem került sor, mivel a zsidó vallási szokások tiltják az exhumálást. Az amerikai hírszerző hivatal, a CIA egy korábbi jelentése szerint viszont nincsen meggyőző bizonyíték arra, hogy Müller valóban Berlinben halt volna meg. „Gestapós Müller" sorsának titka így nagy valószínűséggel továbbra is titok marad.