Узнав о его смерти, участники Пленума, которые слышали его последнюю речь, пустились наперебой превозносить его:
«В тяжелые времена бесконечных заговоров и контрреволюционных выступлений, когда советская земля превратилась в пепел, а пролетариат, борющийся за свою свободу, оказался в кровавом окружении своих врагов, Дзержинский проявил нечеловеческую энергию, день и ночь без сна, без пищи, без всякого отдыха, он стоял на своем посту, его ненавидели враги рабочих, но он смог даже их заставить уважать себя. Его величественная фигура, личная храбрость, проницательность, прямота и исключительная честность снискали ему огромное уважение».
Смерть Дзержинского наступила в очень удобный момент для Иосифа Сталина. К этому моменту он уже практически одержал победу в затянувшейся борьбе за власть, которая последовала за смертью Ленина. «Железный Феликс», даже если бы ему не удалось ничего добиться, наверняка выступил бы против использования ОГПУ как инструмента провокаций и обмана в борьбе с инакомыслящими внутри партии, хотя те же самые методы он, не задумываясь, применял против врагов коммунистов. После смерти Ленина Дзержинский стал председателем Высшего совета народного хозяйства (ВСНХ) и начальником ОГПУ. Безусловно, он выступил бы против нападок на «буржуазных специалистов» в промышленности и жестокой классовой войны в деревне, которую Сталин начнет через несколько лет. В своей «пламенной речи» за три часа до смерти Дзержинский впервые выступил со столь беспощадной критикой в адрес партийного аппарата: «Когда я смотрю на наш аппарат, на нашу систему организации, на нашу невероятную бюрократию и наш крайний беспорядок, опутанный всевозможными проволочками, я буквально прихожу в ужас». На смену Дзержинскому был поставлен Вячеслав Рудольфович Менжинский, высокий, стройный мужчина в позолоченном пенсне, отличавшийся от своего предшественника большей мягкостью. На первый взгляд, эти два человека имели много общего: оба они были старыми большевиками и выходцами из зажиточных польских семей. Менжинский стал членом коллегии ЧК вскоре после ее основания и был назначен первым заместителем Дзержинского, когда тот стал председателем ОГПУ. Пожалуй, он был самым образованным из всех, кто приходил в руководство КГБ. Даже бывший сотрудник ОГПУ Георгий Агабеков, который после побега на Запад не проявлял особой симпатии по отношению к своим бывшим коллегам, говорил о нем как о человеке «глубокой культуры» и «всестороннего образования». По словам Федора Фомина, Менжинский свободно владел двенадцатью языками, когда он был принят на работу в ЧК. Позже он овладел китайским, японским, персидским и турецким языками. Но он проявлял интерес не только к языкам, но и к точным наукам: физике, химии, астрономии, математике. Вместе с тем Менжинский не был тем воплощением силы и власти, каким был его предшественник. Даже Фомин в своих официально одобренных панегириках вынужден был признать, что «у него не было командного голоса». Для многих, кто работал с ним, «было странно слышать приказ от председателя ОГПУ, который обычно начинался словами: „Я покорно прошу…“ Троцкий, преследование которого со стороны ОГПУ началось во времена Менжинского, считал его странной, бесцветной личностью: „Впечатление, которое он произвел на меня, лучше всего описать одним словом – никакое. Он выглядел, как тень какого-то другого, не реализовавшего человека, или, точнее, как плохой набросок к незаконченному портрету.“ Менжинский не был сталинистом. Во время Гражданской войны он встречался с Троцким на фронте и предупреждал, что Сталин ведет „очень запутанную игру“ против него. Однако сам он никогда серьезно не выступал против растущей власти Сталина. Еще до своего нового назначения Менжинский серьезно страдал от астмы. Очень часто он встречал посетителей, лежа на кушетке в своем кабинете на Лубянке. „Доктора приказали мне лежать“, – объяснял он. В апреле 1929 года у Менжинского случился инфаркт, который вывел его из строя на два года.
В 1931 году он вновь начал выполнять свои обязанности, но здоровье не позволяло ему работать в полную силу, а к 1933 году он настолько ослаб, что даже не мог самостоятельно подняться по лестнице в свою комнату в Кремле и вскоре, практически отойдя от дел, поселился на подмосковной даче.
Из-за слабого здоровья Менжинского и его вялого стиля руководства власть в ОГПУ постепенно перешла к его более агрессивному заместителю Генриху Григорьевичу Ягоде, коренастому, пышащему здоровьем еврею, который коренным образом отличался от Менжинского как по своим манерам, так и по внешнему виду. Воспоминания об этом человеке до сих пор не вызывают ничего, кроме стыда, даже среди сотрудников КГБ. Практически во всех мемуарах о сталинской эпохе это имя упоминается с отвращением. «Если Менжинский не имел себе равных по широте образования, Ягода не имел себе равных по жестокости, бескультурью и грубости», – писал Агабеков. Однако его грубость и жестокость еще не проявились столь явно, когда Дзержинский назначил его своим вторым заместителем в 1923 году. Возможно, Дзержинский полагал, что он был просто исполнительным и энергичным бюрократом, полным амбиций. Ягода стал классическим примером бюрократа, испорченного чрезмерной властью. Его растущая претенциозность была под стать его жестокости. Как рассказывал один из сотрудников Ягоды, за несколько дней до того, как он был отстранен от занимаемой должности летом 1936 года, он был полностью поглощен разработкой своей новой служебной формы: белый шерстяной костюм, отделанный золотыми галунами, небольшой позолоченный кортик, как у военно-морских офицеров при царе, голубые брюки и ботинки из специально выделанной импортной кожи.
Сталин никогда полностью не доверял Ягоде, отчасти потому, что сам был антисемитом, и потому, что Ягода симпатизировал «правой оппозиции» и ее популярному лидеру, Николаю Бухарину. В 1928 году в разговоре с Каменевым Бухарин сказал, что и Ягода, и Трилиссер, второй заместитель председателя ОГПУ и начальник ИНО, «были с ними». Он также сказал, что Ягода передал ему секретную информацию о восстаниях крестьян. Вместе с тем Бухарин знал, что Ягода был оппортунистом и что на его поддержку рассчитывать не следовало. В 1931 году Сталин попытался укрепить свое влияние в ОГПУ, направив туда партийного аппаратчика А.И. Акулова, который так же, как и Ягода, занял пост первого заместителя председателя ОГПУ. Но уже через год Акулов был вынужден оставить этот пост. Тем не менее, выжидая удобного момента для того, чтобы поставить своего человека во главе ОГПУ, Сталин смог договориться с Ягодой. Ягода был скорее карьеристом, чем идеологом, и был готов пойти за Сталиным, лишь бы продвинуться по служебной лестнице. Вместе с тем он не был готов безоговорочно поддержать Сталина. Трилиссер же был более активным сторонником «правой оппозиции». Уже в 1923 году он присоединился к Бухарину в наступлении на троцкистскую линию. Но к концу 1929 года Ягода, рассматривая Трилиссера как потенциального соперника, смог при поддержке Центрального Комитета добиться, чтобы Трилиссер был убран из ОГПУ. Вместо него на пост главы ИНО был назначен бывший начальник КРО (контрразведка) Артур Артузов.
Первый год пребывания в руководстве ОГПУ Менжинского и Ягоды был отмечен успешным завершением операции «Трест». Однако этот успех был омрачен целым рядом скандальных разоблачений и провалов советской внешней разведки. Безопасность быстро растущей сети ОГПУ и военной разведки была поставлена под угрозу уязвимостью советских шифров, а также неопытностью советских резидентов в организации работы местных коммунистов, которые, отличаясь большим рвением, очень часто действовали по-дилетантски. Весной 1927 года произошло сенсационное разоблачение советской агентуры, работавшей в восьми странах.