10 июля 1945 года маршал Г. К. Жуков, главнокомандующий советскими войсками в Германии и глава Советской Военной Администрации, издал приказ № 2, легализовавший существование «антифашистских» политических партий, таких как КПГ. Пять дней спустя Мильке явился в штаб-квартиру КПГ с предложением своих услуг, заявив, что он уже работает с уличными ячейками КПГ. Заполняя обязательную в таких случаях анкету, Мильке ни словом не обмолвился о своем сотрудничестве с НКГБ, указав ложные данные о своей деятельности во время войны. То, что ему удалось скрыть непреложные факты, доказывает, что он имел абсолютную поддержку Советской Военной Администрации, МГБ и НКГБ. Без такой протекции ложь в анкете могла бы обойтись ему очень дорого.

«Советы безоговорочно доверяли Мильке, — вспоминал Бернд Кауфман, бывший начальник разведшколы Штази. — Он заработал свою репутацию в Испании».

На вопрос анкеты, арестовывался ли он или был судим по политическим статьям, Мильке ответил: «Меня приговорили к смерти заочно». Это была первая ложь. Его имя упоминалось на процессах, проходивших в 1934 году, однако он не был судим. Затем он указал, что после того, как его освободили из лагеря для интернированных лиц — бывших участников гражданской войны в Испании, он перебрался из Франции в Бельгию, где под именем «Гастон» работал в подпольной коммунистической газете.

Третья ложь: Мильке утверждал, что он вернулся во Францию, где под именем Рихард Хебель служил в организации Тодта (чье название он написал неправильно — Тод), полувоенном формировании, которое занималось строительством оборонительных сооружений, аэродромов и дорог и подчинялось вермахту. Он никак не смог бы поступить на службу в эту организацию, находясь за пределами Германии. Весь немецкий персонал набирался в Германии, где личность каждого можно было легко проверить через гестапо.

В вышеупомянутой анкете содержится еще одно доказательство причастности Мильке к расправе над германскими коммунистами, учиненной сталинским НКВД: «Во время моего пребывания в Советском Союзе я участвовал во всех партийных дискуссиях внутри КПГ, а также в обсуждении проблем, касавшихся построения социализма и процессов против предателей и врагов СССР».

Чтобы произвести впечатление на своих новых берлинских товарищей, Мильке похвастал наградами, которые он получил, «включая спортивную медаль СССР». В заключение он написал: «Во время парадов 1 мая и 7 ноября, проходивших на Красной площади, я находился на трибуне для почетных гостей. Я познакомился со многими товарищами из Всемирной федерации коммунистических партий и военного совета специальной комиссии Коминтерна.

Я никогда не забуду свою встречу с товарищем Димитровым, председателем Коминтерна, при котором я и еще один товарищ работали в качестве помощников. Я видел товарища Сталина на всех демонстрациях на Красной площади, особенно когда я стоял на трибуне для почетных гостей. Я упоминаю об этих встречах, потому что все советские товарищи являются для нас образцом для подражания в нашей работе».

Анкеты КПГ передавались в штаб-квартиру МГБ/НКГБ, находившуюся в пригороде Берлина Карлсхорсте. Возглавлял ее генерал-полковник Иван Серов, который через одиннадцать лет получит известность как «Будапештский мясник» за свою роль в подавлении венгерской революции. Как и следовало ожидать, Мильке легко выдержал эту проверку, которая была устроена для отвода глаз непосвященных немецких товарищей. Не будь Серов посвящен во все это дело, Мильке тут же бы арестовали или по меньшей мере подвергли интенсивным допросам в связи с его работой в нацистской организации Тодта, использовавшей рабский труд военнопленных. Проверка заняла рекордно короткое время, и в конце июня Мильке уже был назначен начальником одного из подразделений вновь создаваемой народной полиции.

Теперь будущее Мильке в новой, сталинской, Германии было обеспечено. Когда 16 августа 1947 года Советская Военная Администрация создала первую германскую политическую полицию — к этому времени уже было ликвидировано нацистское гестапо, — ее начальником был назначен Вильгельм Цайссер, а Мильке стал его заместителем. Советы дали этой организации условное название «Пятый комиссариат», или К-5, и формально (на самом деле К-5 действовал самостоятельно) подчинили его управлению уголовного розыска Народной полиции. Этот камуфляж был необходим, поскольку правила Союзной Контрольной комиссии запрещали возрождение германской политической полиции.

К-5 являлся филиалом советской тайной полиции. Его сотрудниками были тщательно отобранные ветераны КПГ, пережившие нацистский период в Советском Союзе или уцелевшие в концлагерях и тюрьмах. Их задачей было выявление нацистов и антикоммунистов, к числу которых принадлежали и многие члены социал-демократической партии. Мильке и его ищейки выполняли эту задачу с безжалостным рвением. Арестовано было столь много людей, что их некуда было сажать. И тогда Серов приказал снова открыть одиннадцать концлагерей, в том числе бывшие нацистские лагеря смерти Бухенвальд и Заксенхаузен.

Вплоть до весны 1946 года население советской оккупационной зоны воспринимало волну арестов как должное, полагая, что объектами расправы бьши бывшие функционеры НСДАП и военные преступники. Затем по настоянию Советов произошло слияние КПГ и социал-демократической партии, которая была заклятым врагом коммунистов со времени Германской революции 1918 года. Новая партия стала называться Социалистической единой партией Германии — СЕПГ. С внешней стороны этот процесс протекал гладко. Однако тысячи рядовых социалистов восприняли это объединение в штыки, за что и были арестованы и брошены в лагеря и тюрьмы. К ним добавили людей, уличенных в антикоммунистических и антисоветских высказываниях. К числу последних принадлежали сотни подростков, которым едва исполнилось четырнадцать лет. Несмотря на то, что лица, производившие аресты, выдавали себя за сотрудников уголовной полиции, существование Пятого комиссариата стало общеизвестным фактом. Мильке повысили в должности, сделав его вице-президентом германской администрации внутренних дел — эквивалент НКВД, и он продолжил свою закулисную деятельность.

Однако дни безвестности Мильке были сочтены. В январе 1947 года, за восемь месяцев до учреждения К-5, два ветерана берлинской полиции узнали Мильке, который присутствовал на каком-то официальном мероприятии. Они рассказали об этом начальнику криминальной полиции Западного Берлина и потребовали ареста Мильке за убийство в 1931 году двух полицейских. Начальник КРИПО (уголовной полиции) доложил о деле Мильке Вильгельму Кюнасту, генеральному прокурору судебной палаты Берлина — высшей судебной инстанции, находившейся в советском секторе. Кюнаст был старым юристом с антинацистским прошлым. Был отдан приказ покопаться в архивах, и к немалому удивлению Кюнаста оказалось, что вся документация процесса 1934 года уцелела, несмотря на бомбардировки союзной авиации. Фамилия Мильке постоянно фигурировала в показаниях свидетелей, изобличавших его как одного из убийц капитанов полиции Анлауфа и Ленка. 7 февраля 1947 года генеральный прокурор подписал новый ордер на арест Мильке.

В то время городская администрация и полиция находились под контролем Союзной Контрольной комиссии, состоявшей из представителей США, Англии, Франции и СССР. О всех своих действиях городские власти, в том числе и правоохранительные органы, должны были уведомлять эту комиссию. Советский представитель тут же известил МГБ. Результаты не заставили себя ждать. Преемник Жукова маршал Василий Соколовский выразил протест, а советские члены комиссии начали кампанию по дискредитации Кюнаста. Против него были выдвинуты многочисленные обвинения. Кюнаст, как утверждали Советы, подозревался в уголовных преступлениях и сотрудничестве с нацистским народным судом, председателем которого был Герхард Фрайслер, самый кровожадный судья Третьего рейха, пославший на смерть сотни антифашистов. Эта наглая ложь показывает, как низко в нравственном отношении могут опуститься Советы ради спасения своего агента. Нападки Советов были столь энергичными, что три западные державы согласились сместить генерального прокурора и заключить его под домашний арест. В то же самое время Советы конфисковали все документы по этому делу, включая протоколы судебных заседаний 1934 года. Мильке мог на время перевести дух. МГБ ценило его услуги и планировало и дальше использовать его для решения еще более важных задач в процессе сталинизации Восточной Германии.