В Харькове, до 1939 года столице советской Украины, в центральном аппарате заметили перспективных работников, и в октябре 1925 года Леплевского первым выдвинули на более ответственный участок, назначив начальником губернского ГПУ в Одессе. Он в свою очередь не забыл способного агентуриста-разработчика Люшкова и рекомендовал в центральный аппарат: свои люди наверху всегда нужны. На должности начальника информационно-осведомительского отдела (ИНФО) ГПУ Украины Люшков просидел целых пять лет. Несмотря на то что ему удалось раскрыть «террористическую группу», готовившую покушение на председателя ВУЦИК Г. Петровского, эти заслуги так и не были оценены. В круг соратников председателя ГПУ он не входил, но все изменилось с приходом в Харьков на должность начальника Секретно-оперативного управления ГПУ Украины старого покровителя — Леплевского.

Вскоре, 3 мая 1930 года, Люшков был назначен начальником СО СОУ ГПУ УССР и наконец попал в номенклатурную обойму. Под руководством Леплевского он принимал самое активное участие в оперативной разработке подпольных «контр революционных, повстанческих организаций: «Украинского национального центра», «Военно-офицерской организации» (дело «Весна») и других. Эта их работа не осталась незамеченной. Новый председатель ГПУ УССР В. Балицкий так оценил вклад в нее Люшкова: «Личные выезды т. Люшкова в районы, руководство агентурой, результативные допросы ряда крупных фигурантов во многом способствовали раскрытию и ликвидации упомянутых организаций» [25] .

Не обошли стороной и покровителя Люшкова — Леплевского. В его адрес Балицкий не жалел громких слов и подчеркивал, что «…благодаря исключительной энергии, четкости и оперативному руководству и непосредственному участию в практической работе со стороны т. Леплевского были ликвидированы крупные контрреволюционные организации» [26] .

Однако через шесть лет и Леплевский с Балицким, стравленные Сталиным и Ежовым, терзали друг друга, как пауки в банке, а спецгруппы НКВД рыскали по всей стране и вылавливали их выдвиженцев. Но тогда, в начале 1930-х годов, Украина и они сами гремели своими результатами в борьбе с контрреволюцией, и этот гром услышали в Кремле.

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

Люшков сразу понял, куда подул ветер, и с учетом прошлого опыта принялся плести вокруг Шеболдаева плотную оперативно-осведомительскую сеть. Но тот оказался тертым калачом, по-крупному нигде не подставился. Тогда Люшков зашел с другой стороны: начал разработку его ближайшего окружения — Белобородова и Глебова. Осведомители ловили каждое неосторожно оброненное ими слово в адрес Сталина и критические высказывания в адрес генеральной линии. Сын портного знал, как шить политические дела, и к ноябрю 1936 года, помимо троцкистов и зиновьевцев Белобородова и Глебова, в тюрьме УНКВД оказалось свыше двухсот человек.

Результаты проделанной Люшковым «работы» оценили не только в наркомате НКВД, но и выше. 2 января 1937 года Политбюро ЦК ВКП (б) приняло специальное постановление «Об ошибках секретаря Азово-Черноморского края т. Шеболдаева и неудовлетворительном политическом руководстве крайкома ВКП (б)». После такого разгромного постановления судьбы Белобородова, Глебова и остальных «коммунистов-перерожденцев» были решены. Не избежал их участи и сам Шеболдаев. Сработала известная схема: сначала его задвинули в курский обком, потом сняли с должности, исключили из партии и репрессировали.

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

Наряду с политической задачей — зачисткой парторганизации края — перед Люшковым стояла и другая, не менее важная задача, связанная с оперативным обеспечением безопасности Сталина во время его пребывания на спецобъектах — черноморских госдачах. Один из таких спецобъектов — «Сосновая роща» — строился в Сочи.

Перед его сдачей Люшков оттуда не вылезал, вместе с архитектором М. Мержановым подчищали последние хвосты. Приехав на объект, Хозяин остался доволен, и похвала не заставила себя ждать: 3 июля 1937 года Люшков был награжден орденом Ленина. Казалось бы, трамплин в Москву готов, но неудача свалилась оттуда, откуда ее не ждали.