Будущий глава гестапо родился 28 апреля 1900 года в Мюнхене. В годы Первой мировой войны служил летчиком, а после ее окончания, в 1919 году, поступил на службу в баварскую полицию. Так получилось, что именно в это время шло разбирательство случаев расстрела заложников — мирных жителей, учиненных бойцами только что свергнутой в Баварии Красной республики. Вероятно именно это, а также то, что Мюллер родился и вырос в глубоко верующей католической семье, обусловили его ненависть к коммунистам, которая нашла свое отражение в работе — в 20-е годы будущий шеф гестапо отвечал за антикоммунистический сектор в политическом отделе полиции Мюнхена. По отзывам самих национал-социалистов, которые также иногда попадали в те времена под его горячую руку, он был ярым противником коммунистов и уже тогда не был склонен строго придерживаться закона в своих действиях.
Вальтер Шелленберг, оставивший в своих мемуарах яркие описания высших руководителей государства и партии, нарисовал такой портрет шефа гестапо: «Мюллер был сухим и скупым на слова, которые он произносил к тому же с типичным баварским акцентом. Я не мог избавиться от чувства, что этот низкорослый, приземистый рейхскриминальдиректор с угловатым крестьянским черепом, узкими, крепко сжатыми губами и пронзающими насквозь карими глазами, которые почти всегда были полуприкрыты, постоянно мигающими веками, не только производил на меня отталкивающее впечатление, но беспокоил меня и нервировал. Особенно неприятно подействовал на меня вид его массивных широких рук с толстыми угловатыми пальцами».
В течение 1933 года Мюллер работал под руководством Гейдриха, который, безусловно, составил о нем определенное мнение. Именно поэтому весной 1934 года, в то время как баварские политические руководители были уверены в его скором увольнении из политической полиции, он не только не ушел на покой, но был призван шефом СД занять место на острие борьбы с инакомыслящими.
Гейдриха не смутили ни аполитичность Мюллера, ни антинацизм Губера, никакие другие обстоятельства. Он был уверен, что призываемые им в Берлин профессионалы будут преданы работе, не обременяя при этом себя излишней приверженностью закону, и вновь оказался прав.
Делегация из Мюнхена не была единственной в своем роде. Так, шеф СД призвал к себе на работу так называемую группу Артура Небе — полицейских из берлинской криминальной полиции. Перед приходом в новую создаваемую структуру Небе успел побороться в столице Германии и с наркотиками, и с воровством, примкнув к национал-социалистам в 1931 году, в период восхода партии.
К третьей условной группе сотрудников, которых удалось привлечь Гейдриху, принадлежали полицейские-профессионалы из самых разных частей Германии. Был среди них и Вернер Бест. Именно ему принадлежит авторство над теми самыми «боксгеймскими документами», которые в 1931 году наделали так много шума после их захвата и обнародования властями. Действовал тогда Бест действительно по своей личной инициативе. А показывал он бумаги своим идейным товарищам как раз на ферме Боксгейм. Один из присутствовавших оказался провокатором и сообщил об инициативе Беста полиции. Вскоре после этого его лишили юридической практики. После мытарств и нужды он в итоге вступил в СС и стал начальником управления СД по Южному региону (югу страны). И вот, в 1934 году он, как и многие другие, был вызван Гейдрихом в Берлин.
Гестапо. Ставка на страх, кругом враги
В развитии гестапо Гейдрих изначально делал ставку именно на страх. Известны его слова о том, что политическая полиция должна вызывать у немцев «страх и трепет». Именно такая репутация, по его мнению, была способна сделать ее эффективным орудием в руках нового режима в борьбе с инакомыслием.
К весне 1934 года, кода шеф СД встал у руля спецслужбы, основы ее организационной структуры были уже заложены Герингом и предшественником Гейдриха — Дилсом. Политическая полиция стала независимой (ранее она входила в состав общей системы охраны порядка). Основными органами стали III отдел гестапо — политический сыск и IV отдел — контрразведка в самом широком смысле слова. Еще при Геринге служба подчинялась непосредственно ему самому. Имперские власти не имели право вмешиваться в ее деятельность.
Такая бесконтрольность вкупе с указом президента Германии от 28 февраля 1933 года «О защите народа и государства», отменявшем основные гражданские права и разрешавшем полиции производить домашние обыски, аресты, подслушивание телефонных разговоров и просмотр писем без решения суда, сделали из гестапо всемогущую организацию, внушающую страх совершенно обосновано.