Born 1900 in Munich. A professional police officer, he had, prior to the 1933 seizure of power, been active in persecuting the NSDAP. After the Nazis came to power in 1933, Reinhard Heydrich recruited Muller, Franz Josef Huber and Josef Albert Meisinger referred to as the "Bajuwaren-Brigade" (Bavarian Brigade).
By 1936, with Heydrich head of the Gestapo, Muller was its operations chief. In September 1939, when the Gestapo and other police organizations were consolidated under Heydrich into the Reich Main Security Office (RSiHA), Muller was made chief of the Gestapo (RSiHA Amt IV).
In this capacity he approached his superior Heinrich Himmler in 1943 with evidence of the disloyalty of Admiral Wilhelm Canaris of the Abwehr. Disappointed with the lack of response, Muller became something of an ally of Arthur Nebe in turning against Himmler and the lack of professionalism of the SS-dominated police forces.
After the Himmler-Putsch, Muller collaborated with Nebe in rooting out traitors in the various police forces, ably assisted by his subordinate and successor, Alois Brunner.