Люшков родился в 1900 году в Одессе в семье еврейского портного. В июле 1917 года вступил в РСДРП(б), затем рядовым в Красную гвардию. С 1918 года в органах ЧК. В 1920 году, т. е. в возрасте 20 лет, он становится заместителем председателя Тираспольской ЧК, в 1924 году – начальником Проскуровского (так до 1954 года назывался город Хмельницкий) окружного отдела ГПУ, входившего в Подольский губернский отдел, которым тогда руководил Израиль Моисеевич Леплевский – также выходец из бедной еврейской семьи рабочего-табачника, в молодости член «Бунда». Не имея образования, Леплевский в 1929 году возглавил Секретно-политический отдел (СПО) ГПУ Украины и забрал к себе в Харьков (тогдашнюю столицу Украины) Люшкова, который стал преемником Леплевского на этом посту. В 1931 году они оба вместе с председателем ГПУ Украины Всеволодом Аполлоновичем Балицким переезжают в Москву, где Балицкий становится заместителем председателя ОГПУ СССР, Леплевский – начальником Особого отдела (ОО) ОГПУ СССР, а Люшков – помощником начальника Секретно-оперативного управления ОГПУ СССР, начальником которого тогда был Генрих Григорьевич (Енох Гершенович) Ягода. Все эти люди сыграют в дальнейшей судьбе Люшкова решающую роль.
В июле 1934 года был образован НКВД СССР, который возглавил Ягода. И уже в декабре того же года Люшков вместе с Ягодой участвует в расследовании убийства Кирова. Таким образом, именно Ягода, а не Леплевский делает Люшкова проходной фигурой – в дамки. Леплевского, наоборот, как и Балицкого, понижают – возвращают на Украину, причем Леплевского вскоре ссылают в Саратов. Хотя в 1937 году его ожидает новый взлет – он станет наркомом внутренних дел Украины.
Уже после своего бегства в Японию, 13 июля 1938 года, Люшков в интервью японской газете «Ёмиури симбун» заявит: «Я действительно предатель. Но я предатель только по отношению к Сталину… Таковы непосредственные причины моего побега из СССР. Я не только непосредственно занимался расследованием убийства Кирова, но и активно принимал участие в публичных процессах и казнях, проводившихся после кировского дела под руководством Ежова. Я имел отношение к следующим делам:
1. Дело так называемого ленинградского террористического центра в начале 1935 г.
2. Дело террористического центра о заговоре против Сталина в Кремле в 1935 г.
3. Дело так называемого троцкистско-зиновьевского объединенного центра в августе 1936 г.
Перед всем миром я могу удостоверить с полной ответственностью, что все эти мнимые заговоры никогда