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