Таубмэн констатирует, что при Хрущеве были арестованы все члены украинского политбюро, оргбюро и секретариата ЦК компартии. Все украинское правительство было смещено, все партийные руководители областей и их заместители были смещены, сняты все руководители военных округов РККА. Из 86 членов ЦК избранных в июне 1938 года, только трое уцелело через год. В 1938 году, то есть в первый год пребывания Хрущева на первом посту на Украине, в республике по политическим мотивам было 106 119 человек было арестовано. Всего с 1938 по 1940 год там было арестовано 165 565 человек. Однако далеко не все аресты, которые требовал Хрущев, были санкционированы в Москве. В 1938 году Хрущев послал жалобу Сталину: "Украина ежемесячно посылает 17-18 тысяч репрессированных, а Москва утверждает не более 2-3 тысяч. Прошу принять срочные меры".
Главным помощником Хрущева в осуществлении репрессий стал новый нарком внутренних дел УССР Успенский. П.Судоплатов подчеркивал, что Хрущев "взял с собой на Украину" Успенского "в качестве главы НКВД. В Москве он возглавлял управление НКВД по городу и области и работал непосредственно под началом Хрущева… Успенский несет ответственность за массовые пытки и репрессии, а что касается Хрущева, то он был одним из немногих членов Политбюро, кто лично участвовал вместе с Успенским в допросах арестованных".
Поэтому бегство Успенского, который почувствовал, что его могут арестовать за осуществление незаконных репрессий, серьезно ударило и по Хрущеву. После того, как Успенский был обнаружен и арестован, он, по свидетельству Судоплатова, "во время допроса показал, что они с Хрущевым были близки, дружили домами". Поэтому, когда приговоренная к смертной казни за пособничество мужу в побеге супруга Успенского написала прошение о помиловании, Хрущев, как писал Судоплатов, "рекомендовал Президиуму Верховного Совета отклонить ее просьбу". Как отмечал Судоплатов, такое "вмешательство" было "способом избавления от нежелательных свидетелей".
На место репрессированных спешно выдвигались новые кадры. Вспоминая свою поездку в Запорожье и Днепродзержинск, Хрущев замечал: "В Днепродзержинске познакомился с группой партийных работников и инженеров, в том числе с Брежневым. Мы стали выдвигать последних на партийную работу, формировать партруководство… Помимо Брежнева из Днепродзержинска выдвинули еще одного человека, секретаря партии по пропаганде". Своих выдвиженцев Хрущева ставил на многочисленные вакантные места в руководстве областей, республиканских наркоматов, крупных предприятий. Он рассчитывал на их лояльное отношение к нему.
Хотя большую часть 1938 года Хрущев провел на Украине, его положение кандидата в члены Политбюро ЦК ВКП(б) требовало от него частых поездок в Москву. Помимо официальных заседаний Хрущев участвовал и в неформальных встречах ведущих руководителей страны. Он вспоминал, как во время одного из своих визитов "как-то в воскресенье Ежов пригласил меня и Маленкова на дачу, там были и Берия. Это случалось не раз". Хрущев познакомился с Л.П.Берией еще в начале 30-х годов. Он вспоминал: "Когда я работал в Москве, то у меня сложились с Берией хорошие, дружеские отношения. Это был умный человек, очень сообразительный. Он быстро на все реагировал и этим мне нравился. На пленумах ЦК мы сидели всегда рядом и перекидывались репликами по ходу обсуждения вопросов либо о тех или других ораторов, как это всегда бывает между близкими товарищами". Еще в 1934 году Хрущев был гостем Берии во время своего пребывания в Грузии.
Еще раньше Хрущев сблизился с Ежовым. По его словам, Хрущев познакомился с Ежовым "в 1929 году, во время обучения в Промышленной академии, и часто встречался с ним по делам академии. Она находилась в ведении ЦК партии, а в ЦК кадрами занимался как раз Ежов… Он был простой человек, питерский рабочий, а тогда это имело большое значение, – рабочий, да еще питерский". Хотя с Маленковым Хрущев познакомился позже, знакомство с ним позволяло Хрущеву решать многие острые кадровые вопросы. Приводя различные примеры такого рода, Хрущев вспоминал: "Тогда это была большая поддержка со стороны ЦК в лице Маленкова: он "сидел на кадрах". Связи с Ежовым, Берией и Маленковым Хрущев старался использовать для укрепления своего положения.