Встревоженный событиями в Восточной Германии, Берия, возглавлявший к тому времени министерство внутренних дел, которое пришло на смену МГБ, вылетел в Берлин. Он хотел знать, почему его сотрудники в ГДР, самом важном внешнем форпосте Советов, не смогли распознать признаки недовольства, дошедшего до своей критической точки, и не приняли превентивных репрессивных мер, которые предотвратили бы восстание. Он провел совещание с министром ГБ Цайссером и его заместителем Мильке, которых хорошо знал еще с начала 30-х. Следует отметить, что здесь, как, впрочем, и всегда в непредсказуемых обстоятельствах, Мильке вел себя с большой осмотрительностью. Ему было известно о крепких узах, связывавших Цайссера с Берией в течение трех десятилетий. Берия решил сместить несколько сот офицеров МВД, включая генерал-майора Ивана Фадейкина, представителя МВД в ГДР. Пострадала лишь горсточка сотрудников, да и то на периферии, уволенных из органов за халатное отношение к своим обязанностям. Один из высокопоставленных офицеров Штази застрелился.
Спокойствие вернулось на улицы советской зоны, однако количество побегов на Запад продолжало расти. Из 331 390 лиц, бежавших в 1953 году, 8000 были служащими частей Народной полиции, находившихся на казарменном положении, которые фактически стали зародышем будущей восточно-германской Народной армии. В числе бежавших были также 1718 членов и кандидатов в члены СЕПГ, правящей партии Восточной Германии.
В коммунистической партии и правительстве выявились разногласия. Макс Фехнер, министр юстиции, заявил, что результатом восстания явились «незаконные аресты». Принадлежность к забастовочному совету или подозрение в том, что тот или иной человек является зачинщиком беспорядков, по мнению министра юстиции, не давали достаточных оснований для ареста и предания суду.
Зато у Мильке появилось достаточно оснований для ареста самого Фехнера. Министром юстиции была назначена Хильда Беньямин, которую, после того как она председательствовала на нескольких показательных процессах, прозвали «Красной Хильдой» или «Красной Гильотиной». Фехнера предали суду как «врага партии и государства». Он провел три года в Баутцене, печально известной тюрьме Штази. Эта тюрьма получила прозвище «желтая беда», потому что в этом желтом здании политзаключенные содержались в самых нечеловеческих условиях.
Вскоре после возвращения в Москву из инспекционной поездки в Берлин был арестован министр внутренних дел СССР Лаврентий Берия, которого обвинили в попытке свержения нового советского руководства. Мильке, то ли вдохновленный арестом Берия, то ли получив прямые указания из Москвы, использовал недавнее восстание как доказательство неспособности своего босса и товарища-чекиста, министра госбезопасности Вильгельма Цайссера обеспечить руководство Штази, Это был удобный предлог, для того чтобы свалить шефа и самому сесть на его место. На заседании партийной комиссии, искавшей козлов отпущения, Мильке заявил, что Цайссер выступал за перемены в партийном руководстве. Он также обвинил Цайссера в том, что тот призывал к сближению с Западной Германией, потому что «считал, что Советский Союз оставит ГДР». В действительности же Цайссер сказал, что «оставаться верным Советскому Союзу всегда, как в хорошие времена, так и в плохие — высший долг коммуниста… Даже если завтра Советский Союз оставит ГДР, нужно хранить верность ему».
Партия решила поверить Мильке. Цайссера сняли с должности, вывели из состава Политбюро и Центрального Комитета и исключили из партии. Мильке, должно быть, ожидал, что в благодарность за преданность Советскому Союзу и партии его вознаградят постом министра госбезопасности. Вместо этого партия решила реорганизовать структуру правоохранительных органов и понизила статус МГБ, подчинив его министерству внутренних дел. Новым главой секретариата государственной безопасности стал Эрнст Волльвебер, известный на Западе как «жалкое существо с мозгами злого ученого». Мильке остался его заместителем.
Со времени своего возвращения из Советского Союза в 1945 году Волльвебер не занимал никаких постов в тайной полиции. Во всяком случае, об этом ничего не известно. Вместо этого он занимал различные должности в министерстве транспорта. Непосредственно перед назначением на пост главы госбезопасности он возглавлял государственный секретариат морского транспорта. В этом качестве он использовал свой опыт минирования судов для введения в учебный план училища торгового флота ГДР специального курса. Из каждого выпуска курсантов, состоявшего из двухсот человек, отбирались двадцать, которых обучали работе со взрывчаткой, а также тому, как вывести из строя двигатели и навигационное оборудование и передавать секретные сообщения. В 1953 году были зафиксированы многочисленные акты саботажа на западных торговых и военных судах, однако твердых доказательств того, что в них были замешаны питомцы Волльвебера, обнаружить не удалось.
Прямым следствием восстания и попыток Цайссера и его сподвижников произвести изменения в руководстве партии и правительстве стало усиление контроля за работой органов госбезопасности со стороны партии. Вальтер Ульбрихт, который занял влиятельнейший пост первого секретаря ЦК СЕПГ, превратил Штази в инструмент удержания личной власти. Ульбрихт запретил вести слежку за ведущими партийными деятелями и вообще вмешиваться в дела партийного аппарата. Мильке стал самым верным слугой Ульбрихта — по крайней мере внешне, как потом обнаружилось, — и объявил МГБ «щитом и мечом государства». Этот девиз не был, однако, гениальным изобретением Мильке. Он просто скопировал его у вновь созданного Комитета государственной безопасности Советского Союза.
Мильке и Волльвебер, который также стал членом ЦК, прекрасно сработались и в течение четырех лет шли в одной упряжке. В их актив следует вписать серьезные успехи в борьбе против организации Гелена, спонсором которой выступало ЦРУ, и американской военной разведки. Одновременно Штази расширило свою сеть тайных информаторов. Щупальца тайной полиции вскоре проникли во все сферы жизни в ГДР. Труды Штази были оценены. В 1955 году Штази вернули статус полноправного министерства, и Мильке получил ранг государственного секретаря.
Мильке вынашивал еще большие амбиции, однако на его пути стоял Волльвебер, Необходимо было как-то его дискредитировать. Мильке знал, что у Ульбрихта были многочисленные разногласия с шефом тайной полиции. Ульбрихт был особенно обеспокоен тем, что Волльвебер основной акцент в работе ведомства делал на контрразведку, а не на контроль за настроениями населения посредством увеличения количества тайных осведомителей. При поддержке Ульбрихта Мильке выступил наконец против Волльвебера, обвинив его в «идеологической подрывной деятельности» против государства и партии. В качестве доказательства Мильке привел контакты своего шефа с высокопоставленными лицами из руководства социал-демократической партии ФРГ, которые стремились к урегулированию отношений с ГДР. Ульбрихт знал, что в Политбюро и Центральном Комитете уже сформировалась фракция, выступавшая против его политики. Эту новую оппозицию возглавил член Политбюро Карл Ширдеван. Волльвебер встал на сторону Ширдевана.
1 ноября 1957 года Волльвебер подал в отставку с поста министра госбезопасности, сославшись на плохое здоровье. В тот же день министром был назначен Мильке. Он сразу же начал перестраивать Штази по образцу и подобию советского КГБ, во главе которого в то время стоял старый наставник Мильке Иван Серов. Перестройка предусматривала в числе прочего введение воинских званий. Ульбрихт присвоил Мильке шание генерал-майора, в котором он и оставался до 1959 года, когда получил повышение и стал генерал-лейтенантом. За год он создал главное управление «А» (внешняя разведка). Заместителем министра в звании генерал-майора и начальником главного управления «А» был назначен Маркус Вольф.
Вольф родился в 1923 году в семье, отличавшейся радикальными коммунистическими убеждениями. После прихода Гитлера к власти он эмигрировал вместе с семьей в Советский Союз, В Москве Маркус посещал среднюю школу имени Карла Либкнехта для детей немецких коммунистов, живших в эмиграции. Утверждают, что еще учеником он завязал связи с ГПУ и доносил на своих учителей. В период сталинских чисток 1936–1938 годов несколько учителей, мужчин и женщин, было арестовано и бесследно исчезло в трудовых лагерях. Однако с полной уверенностью говорить о том, что эти аресты были результатом деятельности юного Вольфа, нельзя. И все же следует заметить, что Вольф и его семья принадлежали к числу тех немногих немецких коммунистов-интеллектуалов, которых чистки обошли стороной.