В середине 1924 г. Мюллер вступает в брак с дочерью владельца издательства и типографии Отто Гишнера Софией (1900-1990), сторонника Баварской народной партии, вполне консервативной и антисоциалистической, державшей власть в Баварии с 1920 по 1933 г. С будущей женой Мюллер познакомился в 1917 г., в период военной службы. От этого брака Мюллер имел сына и дочь. Брак оказался несчастливым из-за его постоянной занятости работой. Он редко бывал дома. До середины 1924 г. жил у своих родителей, затем, до переезда в Берлин, был формально прописан у родителей жены, какое-то время жил с семьей отдельно на улице Лютцовштрассе. Жена разделяла взгляды отца, к наци относилась отрицательно. Оказавшись в Берлине, позволяла себе довольно свободно и критически высказываться в разговорах с соседями — в результате на нее донесли. Ее вызвал для разговора и внушения лично Гейдрих! Софии пришлось замолчать, а Мюллер понял: такая жена будет препятствием в дальнейшей карьере. Поэтому нет ничего удивительного, что он последовательно завел двух любовниц. С первой, Барбарой (1900-1972), он работал в полиции Мюнхена, позже в Берлинском гестапо она ведала делопроизводством. Со второй, Анной, бывшей младше него на 13 лет, он с 1940 г. думал заключить новый брак. Но война с Советским Союзом расстроила все. И даже собственный берлинский дом Мюллера погиб в результате авианалета (к счастью для него, семья спаслась в подземном убежище, предусмотрительно построенном в саду).
При переезде в Берлин Мюллер поселился вначале в пансионе, а затем нашел себе квартиру, куда и перебралась его семья. Несмотря на разногласия с женой, он считался хорошим семьянином.
В новую работу, при покровительстве Гейдриха, Мюллер вошел очень легко. А занял он место еврея Рейнгольда Геллера (1885-1945?), офицера Первой мировой войны, видного работника в полиции, берлинского эксперта по левым движениям, члена НСДАП с 1933 г., члена СС — с 1938 г., криминального советника (в войну руководил полицией Потсдама), соратника Артура Небе.
Как возникли понимание и доверительные отношения с Гейдрихом? Они познакомились во время поездки Гейдриха, тогда штандартенфюрера, в Мюнхен. Друг и сосед Мюллера, д-р Штеппа об этом вспоминает так: «Райнхард Флеш и Генрих Мюллер являлись противниками национал-социализма и были известны как таковые. Познакомившись с ними, Гейдрих сразу почувствовал их интеллигентность. Мюллер был интеллигентным, Флеш — спокойным и невозмутимым. Именно они наладили работу баварской политической полиции, у Гейдриха были идеи, а они воплощали эти идеи в жизнь».
В самом Берлине, в аппарате СС и СД, состоявшем из профессиональных юристов с высшим образованием, куда Мюллера приняли 29 апреля 1934 г. в чине штурмбаннфюрера (майор), появление провинциала баварца, не имевшего академического образования и аристократической родословной, встретили сдержанно, с удивлением, а некоторые — враждебно. Периодически на него писали доносы. Такого, например, рода:
«Как Мюллер дослужился до руководящей должности в СС, нам непонятно. Он никогда не был членом партии. У нас также нет его заявления о вступлении в партию».
Работа, однако, быстро показала, кто чего стоит. С большим удивлением недоброжелатели увидели, что Мюллер:
1. Криминалист высшей квалификации;
2. Имеет феноменальную память;
3. Обладает исключительными организаторскими способностями;
4. Невероятно работоспособен, и у него полностью отсутствует личная жизнь;
5. Убежденный антикоммунист, но и к нацизму относится сдержанно. Проявились и другие стороны личности:
1. Мюллер стал перетаскивать в Берлин своих сотрудников по Мюнхену, которым полностью доверял (37 криминалистов);
2. В личные отношения он ни с кем не вступал, друзей почти не имел, откровенных разговоров, даже среди «своих», часто избегал, выступал чем-то вроде «сфинкса»; с Шелленбергом, заместителем Гейдриха, быстро вошел во враждебные отношения, так как тот не желал подчиняться, несмотря на свою молодость;
3. Будучи вполне послушным в отношении Гиммлера и Гейдриха (первого он не очень любил, но по телефону всегда четко отвечал: «Слушаюсь, рейхсфюрер!»), Мюллер никогда не брал на себя ответственности за те или иные важные акции, но всегда говорил: «Рейхсфюрер приказал»;
4. Он не любил командировок и предпочитал, как бюрократ, работу с бумагами, реагируя на все запросы очень быстро. Против пыток он возражал, а на допросах предпочитал запугивать страшными криками и диким вращением глаз. Своей мимикой он владел блестяще. Мюллер тщательно изучал методы допросов в НКВД и восхищался его работой!