Нойкёльнская гимназия была средней школой, где упор делался на изучение гуманитарных дисциплин. Обучались там в основном дети из обеспеченных слоев общества. Представители рабочего класса допускались туда, только сдав строгие экзамены. Немногим удавалось пройти сквозь это сито. Похоже, что будущий министр госбезопасности обладал достаточными способностями для поступления туда, но не для окончания гимназии. Возможно, дело было в другом: он забросил учебу, будучи слишком занят партийными делами. Как бы то ни было, но, чтобы никто не заподозрил его в буржуазном происхождении, Мильке отметил в автобиографии, что посещал гимназию два года «бесплатно».
Советские инструкторы остались довольны Эрихом Мильке, который схватывал все на лету. Еще до того, как он окончил разведшколу, ЦК КПГ в изгнании рекомендовал его для поступления в элитную Международную ленинскую школу, кузницу идеологических кадров. Учеба в этом заведении была необходимой ступенью в карьере партийного руководителя, особенно такого, кто был отобран для участия в будущих тайных операциях. ОГПУ и Коминтерн одобрили его кандидатуру и дали Мильке новую кличку — «Пауль Бах», которой он пользовался в течение нескольких последующих лет.
Говоря языком мафии, Мильке был «готовым солдатом» ОГПУ и Коминтерна, человеком, способным легко влиться в тайную армию, которая без колебаний и угрызений совести выполняла любые приказы, если речь шла о борьбе за идеалы коммунизма. Потребность в такой армии в те Годы ощущалась более чем когда-либо. В Германии, которая была огромным препятствием на пути к ленинской мировой революции, власть захватил Адольф Гитлер со своими нацистами, и компартии пришлось уйти в подполье. Тысячи партийцев были арестованы и брошены в тюрьмы и концлагеря, сотням удалось скрыться. Руководство КПГ бежало за границу, по большей части в Москву. Мечты немецких коммунистов о «Советской Германии» рассыпались в прах, но они были убеждены, что когда-нибудь возьмут реванш.
В середине марта 1933 года Мильке, учившийся в Международной ленинской школе, получил через ОГПУ известие о том, что берлинская полиция арестовала Макса Тунерта, одного из тех, кто был причастен к убийству Анлауфа и Ленка. Прошли считанные дни, и пятнадцать остальных соучастников оказались в тюрьме. В Москве подробности полицейской акции против берлинских товарищей Мильке стали известны лишь через шесть месяцев.
14 сентября 1933 года берлинские газеты сообщили, что все пятнадцать коммунистов сознались в том, что участвовали в подготовке и осуществлении убийства полицейских. Были выданы ордера на арест десяти других соучастников, которым удалось скрыться, в том числе Мильке, Циммера, Ульбрихта, Киппенбергера и Ноймана.
Циммер также посещал военно-Политическую и Международную ленинскую школы. Ему дали псевдоним «Георг Шлоссер», однако он и Мильке учились в разных группах. В 1934 году они все же оказались вместе в специальной коминтерновской школе, где в течение года преподавали военные и политические дисциплины другим немецким коммунистам, которых в Москве становилось все больше и больше после прихода нацистов к власти. Туда благополучно перебрались Киппенбергер и Нойман. Ульбрихт сбежал в Австрию, где продолжал подрывную деятельность по заданию Коминтерна. В конце концов и он эмигрирует в Москву.
Окунувшись с головой в работу в школе Коминтерна, Мильке не располагал временем, чтобы как следует осмыслить значение судебного процесса 1934 года, на котором Клаузе, Матерн и Бреде были приговорены к смертной казни. Остальные получили сроки от девяти месяцев до пятнадцати лет каторжных работ. Матерна гильотинировали, а Бреде повесился в тюремной камере. Клаузе помиловали, заменив ему смертную казнь пожизненным заключением, потому что, как было сказано в судебном приговоре, он «оказал ценную помощь следствию». В глазах Мильке Клаузе и четверо других подсудимых, которые были оправданы или освобождены за недостатком улик, оказались предателями общего дела.
Все это время Мильке поддерживал тесные связи с советской тайной полицией, которая теперь стала называться народным комиссариатом внутренних дел (НКВД). Его возглавил Генрих Григорьевич Ягода, бывший заместитель начальника ОГПУ Вячеслава Рудольфовича Менжинского, скончавшегося в 1934 году.