Единственной частью государственного аппарата, которая могла помочь Сталину в подготовке этого убийства, являлось ленинградское управление НКВД, отвечавшее за безопасность Кирова. Но начальником этого управления был Филипп Медведь, связанный с Кировым тесной дружбой. Медведя следовало убрать и заменить другим человеком, «более надёжным». У Сталина был на примете такой человек: Евдокимов, давний сотрудник «органов». Несколько лет подряд Сталин брал его с собой в отпуск — не только в качестве телохранителя, но и как приятеля и собутыльника. Евдокимов получил от Сталина больше наград, чем любой другой энкаведист. Это была странная личность с застывшим, точно окаменевшим лицом, сторонившаяся своих коллег. В прошлом заурядный уголовник, Евдокимов вышел из тюрьмы благодаря революции, примкнул к большевистской партии и отличился в гражданской войне. Когда война закончилась, Евдокимов был назначен начальником областного управления ОГПУ на Украине. Там он лично возглавлял карательные операции против антисоветских повстанческих банд.
По распоряжению Сталина Ягода издал приказ о переводе Медведя из Ленинграда в Минск и назначении Евдокимова на его место. Узнав об этом, Киров пришёл в негодование. В присутствии Медведя он позвонил Ягоде и без обиняков начал допытываться, кто дал ему право перемещать ответственных ленинградских работников без разрешения ленинградского обкома. Затем Киров позвонил Сталину и опротестовал недопустимый образ действий Ягоды. Приказ о переводе Медведя из Ленинграда пришлось отменить.
Поскольку с назначением Евдокимова в Ленинград ничего не получилось, у Сталина не было иного выбора, как обратиться за помощью к Ягоде и посвятить его в свои тайные планы, касавшиеся Кирова. Ягода сразу же вызвал из Ленинграда своего протеже и фаворита Ивана Запорожца, который в то время был заместителем Медведя. Они посетили Сталина вдвоём. Избежать личного разговора Сталина с Запорожцем было нельзя: последний никогда не взялся бы за такое чрезвычайное задание, касающееся члена Политбюро, если б оно исходило всего лишь от Ягоды и не было санкционировано самим Сталиным. Получив сталинский наказ, Запорожец вернулся в Ленинград.
Как раз в это время среди бумаг, поступающих в ленинградское отделение НКВД, оказалось секретное донесение, касавшееся молодого коммуниста по имени Леонид Николаев. Этот Николаев был так обозлён тем, что его исключили из партии и связанной с этим невозможностью устроиться на работу, что у него появилась мысль об убийстве председателя комиссии партийного контроля. Этим актом доведённый до отчаяния Николаев намеревался выразить свой протест против партийной бюрократии, чьей жертвой он себя считал.
Донос на Николаева поступил в «органы» от его друга, которому он имел неосторожность рассказать о своих намерениях. В этом, конечно, не было ничего удивительного. Закономерным было и то, что Запорожец, озабоченный полученным в Москве заданием, заинтересовался личностью Николаева. Встретившись с его «другом» и поговорив с ним, он пришёл к выводу, что слова Николаева не приходится считать пустой болтовней. Дело приняло ещё более серьёзный оборот, когда «друг» выкрал и принёс Запорожцу дневник Николаева.
Дневник был сфотографирован и снова подброшен туда, откуда был украден. На его страницах Николаев подробно описывал свои злоключения: как он был беспричинно «вычищен» из партии, какое бездушное отношение встречал со стороны партийных чинов, когда пытался добиться справедливости, как его уволили с работы и до какой жуткой нищеты докатилась его семья — двое детей, жена и мать. Записи дневника были полны клокочущей ненависти к бюрократической касте, воцарившейся в партии и государственном аппарате.
Чтобы получить возможно более полное представление о личности Николаева, Запорожец решил лично встретиться с ним. Всё тот же «друг» организовал ему якобы случайную встречу с Николаевым, представив Запорожца под вымышленным именем, как своего бывшего сослуживца. Поболтав о том, о сём, они расстались. Николаев произвёл на Запорожца благоприятное впечатление. Теперь «другу» была поставлена новая задача: попытаться ещё более сблизиться с Николаевым, время от времени передавать ему небольшие суммы денег, прикинуться разделяющим его взгляды — и, конечно, сообщать НКВД о каждом его шаге. Сам Запорожец поспешил в Москву поделиться соображениями о том, как лучше использовать подвернувшийся случай. Там он ещё раз был принят Сталиным.