В том же году был переведён в центральный аппарат ОГПУ. Вёл допросы и утвердил обвинительное заключение по сфабрикованному ГПУ делу «Российской национальной партии». В декабре 1934 г. участвовал в расследовании убийства С. М. Кирова (впоследствии, перебежав к японцам, заявил, что убийца Кирова Л. В. Николаев был психически больным человеком, а не участником террористической зиновьевской организации, на которую выводило следствие). Пользовался расположением наркома внутренних дел в 1934–1936 гг. Г. Г. Ягоды. В 1935–1936 гг. участвовал в таких громких расследованиях, как «Кремлёвское дело» и «дело троцкистско-зиновьевского центра». По завершении последнего был назначен начальником УНКВД по Азово-Черноморскому краю (до 1937 г.). Руководил развёртыванием Большого террора в Причерноморье. Входил в состав краевой тройки, активно участвовал в репрессиях. В начале июня 1937 г. награждён орденом Ленина.

В 1937–1938 гг. – начальник управления НКВД по Дальнему Востоку. Приезд Люшкова в Хабаровск по времени совпал с началом массовой операции НКВД, согласно печально известному приказу № 00447. На месте Люшков энергично принялся за работу и параллельно с массовыми репрессиями населения проводил чистку местного УНКВД (были арестованы около 40 сотрудников местного НКВД, в том числе прежний руководитель Дальневосточного УНКВД Т. Д. Дерибас и глава треста «Дальстрой» Э. П. Берзин. Им инкриминировали создание правотроцкистской организации в органах внутренних дел Дальнего Востока). Люшков был главным организатором депортации корейцев с Дальнего Востока, а также репрессий против представителей других наций.

В декабре 1937 г. избран депутатом Верховного Совета СССР от Дальневосточного края, приезжал в Москву на его Первую сессию в 1938 г. Люшков был самым высокопоставленным выдвиженцем Ягоды, который долгое время сохранял позиции после его опалы. Более того, новый нарком Ежов всячески защищал его имя от компромата (арестованные с Ягодой чекисты часто называли вместе с фамилией бывшего наркома фамилию Люшкова). Зам Ежова Фриновский выражал сомнения в необходимости оберегать Люшкова, однако Ежов переубедил своего заместителя. Высказывал политическое недоверие Люшкову и маршал В. К. Блюхер.

В конце апреля 1938 г. был арестован И. М. Леплевский – один из ближайших соратников Люшкова, а чуть позже за укрывательство брата-троцкиста вызван в Москву и арестован заместитель Люшкова М. А. Каган.

26 мая 1938 г. Люшков был освобождён от обязанностей начальника Дальневосточного УНКВД якобы в связи с реорганизацией ГУГБ НКВД и назначением в центральный аппарат. Ежов сообщил ему об этом в телеграмме, где просил высказать отношение к переводу в Москву. Текст телеграммы выдавал, что в действительности его отзывали для ареста (конкретная должность не предлагалась, выяснялось только желание работать в центре вообще, о чём при назначениях не спрашивали; почему-то специально говорилось о подборе преемника). В июне 1938 г. на Дальний Восток прибыли М. П. Фриновский и Л. З. Мехлис для проведения чистки руководства Тихоокеанского флота, погранвойск и местного НКВД.