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