Heinrich Alois Müller urodził się 28 kwietnia 1900 r. w Monachium. Był jedynym dzieckiem urzędnika administracji i żandarmerii Aloisa Antona Müllera i Anny Müller z domu Schrandl. Wychowywany w surowej, katolickiej atmosferze domu rodzinnego, uczęszczał do szkół powszechnych w Ingolstadt, Schrobenhausen i Krumbach. W dokumentach szkolnych był określany jako uczeń zdolny, inteligentny i wyrastający ponad przeciętność. Nauczyciele podkreślali, że interesował się głównie sprawami technicznymi. Z tego powodu 14-letni Heinrich został zatrudniony jako monter samolotowy w firmie Bayerische Flugzeugwerke w Monachium.
11 czerwca 1917 r. jako ochotnik zgłosił się do wojska w bawarskim oddziale pilotów polowych. Naukę pilotażu odbywał w Monachium, Augsburgu i Neustadt. W marcu 1918 r. zakończył szkolenie i został wcielony do grupy lotniczej A287. Między marcem a majem brał udział w walkach pozycyjnych, uzyskując stopień podoficera. W tym czasie wsławił się samotnym lotem, podczas którego zrzucił bomby na Paryż, za co został odznaczony Krzyżem Żelaznym II i I klasy. W listopadzie 1919 r., a więc rok po zakończeniu I wojny światowej, zakończył karierę w wojsku, aby 1 grudnia rozpocząć pracę w dyrekcji policji w Monachium. Tam piął się po szczeblach kariery policyjnej, uzupełniając wykształcenie.
Rasowy policjant
17 czerwca 1924 r. Müller ożenił się z Sophie Dischner, córką kierownika wydawnictwa i redaktora monachijskiej gazety „Würmtalbote”. Pismo to było organem Bawarskiej Partii Ludowej o sympatiach prokatolickich. Sophie Müller była działaczką tej partii, ale w miarę awansów męża przestała brać udział w działalności jakiejkolwiek organizacji społecznej. Małżeństwo miało dwoje dzieci – syna i córkę. 1 lipca 1929 r., po dziesięciu latach pracy, Heinrich Müller otrzymał awans na sekretarza policji. Pracował w wydziale politycznym dyrekcji policji w Monachium. Jego specjalnością były obserwacja i zwalczanie ruchów lewicowych na terenie Bawarii. Szczególnie pilnie studiował metody rosyjskiego systemu policyjnego, co pomagało mu w rozpracowywaniu Związku Spartakusa i całego niemieckiego ruchu komunistycznego.
Nie jest przesadą twierdzenie, że perfekcyjny, energiczny i bezwzględny Heinrich Müller stał się ekspertem w zwalczaniu ruchów lewicowych. Potwierdzają to wspomnienia jego osobistej sekretarki Barbary Hellmuth, której dyktował raporty. Zaciekłość w niszczeniu organizacji lewicowych i komunistycznych z pewnością przyczyniła się do rozwoju jego późniejszej kariery w strukturach III Rzeszy, mimo że z zeznań jego współpracowników, Seibolda i Hubera, wynika, że w okresie monachijskim nie był lubiany przez działaczy NSDAP, ponieważ nie chciał wstąpić do partii. Swoich awansów w tym czasie nie zawdzięczał poparciu nazistów, tylko wiedzy w dziedzinie kryminologii i doświadczeniu w walce z komunistami.
Po ostatecznym upadku Republiki Weimarskiej utworzono Bawarską Policję Polityczną, do której został przeniesiony Müller. Wkrótce potem z inicjatywy Hermanna Göringa powstała Tajna Policja Państwowa (Gestapo). Jej urzędnicy wywodzili się ze starych struktur policyjnych, a część została wcielona do Gestapo wbrew swojej woli. 20 kwietnia 1934 r. Heinrich Müller wstąpił do SS i objął stanowisko kierownika wydziału politycznego Gestapo. Jego aktywny udział w nocy długich noży (30 czerwca 1934 r.) zaowocował kolejnymi awansami. Dopiero w 1938 r., kiedy miała zapaść decyzja o mianowaniu go na dyrektora kryminalnego Rzeszy, Heinrich Müller złożył wniosek o przyjęcie w szeregi NSDAP. Spis personalny wyższych oficerów SS z 1 grudnia 1938 r. wskazuje, że wystąpił także z Kościoła katolickiego. 20 kwietnia 1939 r. uzyskał w SS stopień Oberführera. W ramach struktur państwowych został kierownikiem Centrali Rzeszy ds. Wychodźstwa Żydowskiego w Berlinie. W sierpniu 1939 r. mianowano go na dyrektora kryminalnego Rzeszy, a 27 września został szefem Gestapo – Urzędu IV w Głównym Urzędzie Bezpieczeństwa Rzeszy. Zakres jego władzy był ogromny. Obejmował Policję Kryminalną (Kripo), Policję Graniczną (Grepo), Tajną Policję Polową (GFP), Celną Straż Graniczną, Policję Porządkową (Orpo), Policję Ochronną (Schupo i żandarmeria).