В том же году был переведён в центральный аппарат ОГПУ. Вёл допросы и утвердил обвинительное заключение по сфабрикованному ГПУ делу «Российской национальной партии». В декабре 1934 г. участвовал в расследовании убийства С. М. Кирова (впоследствии, перебежав к японцам, заявил, что убийца Кирова Л. В. Николаев был психически больным человеком, а не участником террористической зиновьевской организации, на которую выводило следствие). Пользовался расположением наркома внутренних дел в 1934–1936 гг. Г. Г. Ягоды. В 1935–1936 гг. участвовал в таких громких расследованиях, как «Кремлёвское дело» и «дело троцкистско-зиновьевского центра». По завершении последнего был назначен начальником УНКВД по Азово-Черноморскому краю (до 1937 г.). Руководил развёртыванием Большого террора в Причерноморье. Входил в состав краевой тройки, активно участвовал в репрессиях. В начале июня 1937 г. награждён орденом Ленина.
В 1937–1938 гг. – начальник управления НКВД по Дальнему Востоку. Приезд Люшкова в Хабаровск по времени совпал с началом массовой операции НКВД, согласно печально известному приказу № 00447. На месте Люшков энергично принялся за работу и параллельно с массовыми репрессиями населения проводил чистку местного УНКВД (были арестованы около 40 сотрудников местного НКВД, в том числе прежний руководитель Дальневосточного УНКВД Т. Д. Дерибас и глава треста «Дальстрой» Э. П. Берзин. Им инкриминировали создание правотроцкистской организации в органах внутренних дел Дальнего Востока). Люшков был главным организатором депортации корейцев с Дальнего Востока, а также репрессий против представителей других наций.
В декабре 1937 г. избран депутатом Верховного Совета СССР от Дальневосточного края, приезжал в Москву на его Первую сессию в 1938 г. Люшков был самым высокопоставленным выдвиженцем Ягоды, который долгое время сохранял позиции после его опалы. Более того, новый нарком Ежов всячески защищал его имя от компромата (арестованные с Ягодой чекисты часто называли вместе с фамилией бывшего наркома фамилию Люшкова). Зам Ежова Фриновский выражал сомнения в необходимости оберегать Люшкова, однако Ежов переубедил своего заместителя. Высказывал политическое недоверие Люшкову и маршал В. К. Блюхер.
В конце апреля 1938 г. был арестован И. М. Леплевский – один из ближайших соратников Люшкова, а чуть позже за укрывательство брата-троцкиста вызван в Москву и арестован заместитель Люшкова М. А. Каган.
26 мая 1938 г. Люшков был освобождён от обязанностей начальника Дальневосточного УНКВД якобы в связи с реорганизацией ГУГБ НКВД и назначением в центральный аппарат. Ежов сообщил ему об этом в телеграмме, где просил высказать отношение к переводу в Москву. Текст телеграммы выдавал, что в действительности его отзывали для ареста (конкретная должность не предлагалась, выяснялось только желание работать в центре вообще, о чём при назначениях не спрашивали; почему-то специально говорилось о подборе преемника). В июне 1938 г. на Дальний Восток прибыли М. П. Фриновский и Л. З. Мехлис для проведения чистки руководства Тихоокеанского флота, погранвойск и местного НКВД.
Люшков понял, что это значит, и решил бежать из страны. По имеющимся в настоящее время архивным данным можно с определённой долей уверенности утверждать: Люшков заранее подготовил свой побег. 28 мая он телеграфировал, что благодарит за оказанное доверие и считает новую работу за честь, однако ещё за две недели до этого приказал своей жене взять дочь и следовать в одну из клиник Западной Европы (документы, подтверждающие необходимость лечения дочери, для этой поездки к тому времени были уже готовы). По благополучном прибытии жена должна была прислать Люшкову телеграмму, содержащую текст «Шлю свои поцелуи». Но разработка Люшкова началась уже тогда – жена Люшкова Нина Васильевна Письменная (первая жена Я. В. Письменного – генерал-майора и известнейшего лётчика-испытателя) была арестована 15 июня 1938 г., 19 января 1939 г. осуждена как член семьи изменника Родины на 8 лет лагерей. 15 февраля 1940 г. Особое совещание при НКВД пересмотрело её дело, постановило считать её отбывшей срок и отправило в пятилетнюю ссылку. После реабилитации в 1962 г. она нашла дочь Людмилу Яковлевну Письменную (падчерицу Люшкова) в Юрмале (Латвия), где и прожила до кончины в возрасте 90 лет (1999 г.). Падчерица Люшкова Людмила Письменная после ареста матери и бегства отчима была спасена родной сестрой отца Анной Владимировной (Вольфовной) Шульман (Письменной), после войны с её семьёй переехала в Латвию, где и прожила до своей кончины в 2010 г.