Вместо того чтобы проводить Ульбрихта в зал заседаний, телохранители повели протестующего Ульбрихта на долгую прогулку вдоль реки Шпрее, которая течет за зданием Госсовета. Через час с небольшим телохранители получили по радиотелефону указание привести подопечного на заседание. По прибытии его информировали о том, что первым секретарем ЦК СЕПГ и председателем Совета Национальной обороны избран Эрих Хонеккер. Самого же Ульбрихта избрали председателем Государственного Совета, на должность чисто номинальную, лишенную какой-либо реальной власти.

С избранием Хонеккера на высшие посты в партии и государстве карьера Мильке достигла зенита. В награду за преданность Хонеккер сделал Мильке кандидатом в члены Политбюро и дал ему новый дом в поселке партийной элиты за пределами Берлина. Пять лет спустя Мильке избрали членом Политбюро. Ему также присвоили звание генерала армии.

Из всех глав тайной полиции стран Восточного блока Мильке оставался на своем посту самое продолжительное время. Он был в самых близких отношениях с одиннадцатью начальниками советской тайной полиции и пережил их всех. Беспрекословно выполняя любые их указания, Мильке не моргнув глазом начинал столь же ревностно служить новому хозяину в ту же минуту, как только старого отправляли на тот свет или в отставку. Он был предан не личности, но общей структуре КГБ — Штази ради сохранения и укрепления власти коммунистов, ради коммунистической экспансии.

В своих планах коммунистической экспансии в Западной Европе советское руководство придавало особое значение той части Германии, которую его войска оккупировали с 1945 года. С началом холодной войны советская зона — а позднее «суверенная» ГДР — стала форпостом советской разведки и коммунистическим плацдармом для броска в Западную Европу. Будучи самым западным сателлитом Советского Союза, Восточная Германия находилась на передовой идеологической борьбы против капитализма. Во весь рост встали проблемы не только обеспечения безопасности СССР, предотвращения побегов на Запад и борьбы с деятельностью западных разведок, но и подавления любых настроений антикоммунистического характера среди населения. Штази служила инструментом реализации этих задач, который до середины 50-х полностью находился под советским контролем.

Ключевой фигурой советского контроля был генерал Иван Александрович Серов. В качестве награды за весомый вклад в советизацию Восточной Европы Серов был повышен в должности и в марте 1954 года назначен председателем вновь созданного КГБ. Это было очередное признание заслуг Серова как представителя советских органов безопасности в ГДР, несмотря на восстание 1953 года. Вина за этот провал была возложена на главу тайной полиции Лаврентия Берию и послужила одной из причин его казни. Покидая в конце 40-х годов Германию, Серов оставил после себя хорошо налаженный аппарат, который он передал в надежные руки своего послушного слуги Эриха Мильке.

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

Постепенно менялся характер отношений между КГБ и Штази, переходя с приказного, характерного для первых послевоенных лет оккупации, к «братскому». Этот процесс все более набирал силу по мере того, как Штази показывала свое рвение и добивалась успехов в шпионаже, подрывной деятельности, внешней и внутренней контрразведке. Содружество между обеими службами стало столь тесным, что КГБ предложил своему восточно-германскому союзнику основать в Москве и Ленинграде оперативные базы для наблюдения за гостившими там восточно-германскими официальными лицами и туристами. Офицеры Штази не испытывали никакого комплекса неполноценности в отношении со своими советскими коллегами. Министр Мильке на совещаниях и в официальных директивах постоянно подчеркивал, что офицеры МГБ должны считать себя «чекистами Советского Союза». Он не уставал клясться в абсолютной верности союзу между сотрудниками Штази и КГБ. Навряд ли можно найти хоть одну речь в период между 1946 и 1989 годами, в которой Мильке не отдавал бы дань уважения советским чекистам и не превозносил добродетели братства между КГБ и Штази, даже когда он выступал в сельскохозяйственных кооперативах и на заводах.

В течение двадцати лет отношения между МГБ ГДР и КГБ основывались на неформальных договоренностях между Мильке и главами советских органов безопасности. 29 марта 1978 года был подписан первый официальный протокол о сотрудничестве между КГБ и Штази. Его подписали Мильке и Юрий Андропов, который впоследствии сменил Брежнева в качестве главы государства. Шеф Штази позаботился о том, чтобы офицеры КГБ в Восточной Германии пользовались такими же правами и властью, как и в Советском Союзе, за исключением права арестовывать граждан ГДР. По числу сотрудников резидентура КГБ в ГДР была самой крупной среди всех его зарубежных резидентур и руководила всеми разведывательными операциями в Западной Европе.

Четыре года спустя, 10 сентября 1982 года, председатель КГБ Виталий Федорчук подписал формальное соглашение с Мильке, который обязался взять на себя все техническое обеспечение резидентуры КГБ в Восточной Германии, штат которой насчитывал около 2500 человек. Штази предоставила жилые здания, детские сады, а также автотехнику и ее обслуживание. Виллы и квартиры были полностью обставлены. Сейчас уже невозможно подсчитать, во что это обошлось восточно-германским налогоплательщикам, но сумма затрат наверняка измерялась десятками миллионов марок. В среднем затраты на обстановку одной такой квартиры составляли около 19 тысяч долларов.

Генерал Серов определил местом пребывания представительства КГБ в ГДР Карлсхорст — один из районов Берлина. Там в разное время работало и проживало от 800 до 1200 сотрудников КГБ, включая членов их семей. До середины 50-х весь район представлял из себя тщательно охраняемый военный городок, в котором также размещалась Советская Военная Администрация. Позднее колючую проволоку убрали, но здания комплекса КГБ остались обнесенными двухметровой стеной.

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

Шестой отдел, подчинявшийся второму главному управлению (контрразведка), находился в Цецилиенхофе, в Потсдаме, бывшей летней резиденции прусских королей и германских кайзеров. Там в 1945 году проходила послевоенная конференция союзников, разработавшая основы общей политики в отношении побежденной Германии. Это был мозговой центр советской военной разведки (ГРУ) в Германии, в числе прочего занимавшийся вербовкой жителей Западного Берлина не немецкого происхождения. Эта деятельность играла важную роль в операциях КГБ в Турции и на Ближнем Востоке. Турок и арабов вербовали в Западном Берлине, обучали в Восточной Германии и посылали обратно, на родину. Штази предоставляла учебные центры, конспиративные явки для тайных встреч и снабжала агентов проездными документами.