Генрих Мюллер был родом из Баварии, с квадратной головой крестьянина. Невысокий рост, коренастое телосложение, массивность, тяжелая и слегка покачивающаяся походка выдавали его происхождение. Не блещущий особым умом, но чрезвычайно упорный и упрямый, он избежал неминуемой судьбы пахаря, упорно учась в школе и мечтая стать чиновником. В его среде и окружении эта должность считалась весьма завидной, потому что чиновникам обеспечивалась пенсия. Ему удалось поступить на службу в мюнхенскую полицию. Там Гиммлер заметил его отличительные качества: слепое подчинение дисциплине и профессиональная компетентность. Как все чиновники политической полиции, Мюллер до 1933 года работал против нацистов. Гиммлер не ставил ему это в вину и верил, что он с таким же рвением будет служить новым хозяевам. Мюллер сделал гораздо больше, чтобы заставить забыть о своем прошлом и смягчить враждебность, которую некоторые влиятельные члены партии по-прежнему испытывали к нему. Несмотря на все его старания, целых шесть лет ему упорно отказывали в приеме в партию, членом которой он стал лишь в 1939 году. Так, весьма парадоксальным образом гестапо, главный инструмент обеспечения господства режима, управлялось человеком, чья политическая правоверность не была достаточной, чтобы иметь право считать себя настоящим нацистом. Такой остракизм имел два разных основания: враждебность соперников и расчет хозяев, которые полагали, что Мюллер развернет свою активность еще интенсивнее, чтобы преодолеть сопротивление.
Расчет оказался правильным, и Мюллер из кожи лез вон, чтобы выслужиться. Справедливо отметить, что он легко и искренне воспринял нацистские догмы. Он не был ни интеллектуальным, ни сентиментальным человеком. Под выпуклым лбом лицо его с тонкими холодными губами было жестко, сухо, маловыразительно. Маленькие карие глаза глядели на собеседника пронизывающим взглядом и часто были прикрыты тяжелыми веками. Он брил голову по старой моде, оставляя лишь немного волос на макушке и надо лбом. Руки соответствовали лицу; это были руки крестьянина, квадратные, массивные, широкие, со слегка узловатыми пальцами. Враги говорили, что у него руки душителя.
Мюллер благоговейно почитал силу. Этим объясняется его готовность к исполнению приказов хозяев и то рвение, которым отличались многие его инициативы. Следствием этого культа стала ненависть, которую он питал ко всему, что могло символизировать ум и интеллигентность. Однажды он сказал Шелленбергу, что надо бы бросить всех интеллигентов в угольную шахту и взорвать ее.
Как все новообращенные более позднего периода, Мюллер всегда опасался показаться слабым, поэтому постоянно вступал в соревнования с СД, ненавидя эту службу и подозревая ее в том, что она была причиной его затруднений со вступлением в партию. В профессиональном отношении СД была конкурирующей службой, и Мюллер презирал ее, потому что вначале в ней работали «любители», которых он, старый профессионал политической полиции, без труда превзошел бы.
За такую компетентность Гиммлер начал его уважать. Он доверял Мюллеру до последнего дня и приказал ему остаться в Берлине, когда оттуда эвакуировались все службы. Столь высокая протекция позволила Мюллеру обеспечить и сохранить привилегированное и удивительно независимое положение в системе жесткой иерархии.
Чтобы снискать расположение Гейдриха, он стал исполнителем самых грязных дел, шпионил за своими коллегами, помогая устранять тех, кто стал неугоден. Он участвовал во всех махинациях Гиммлера: ему поручалось доводить до конца большинство «деликатных» миссий. Для таких нужд требовался человек без комплексов и совести, а он и был таковым. Его первой мастерской работой и несомненным «шедевром» стало дело Бломберга – Фрича.