Убийство Кирова, главного потенциального противника Сталина, привело к еще большему усилению власти НКВД. 1 декабря 1934 года Киров был убит выстрелом сзади, когда он выходил из своего кабинета в центральном здании партийной организации Ленинграда. У убийцы Кирова, Леонида Николаева, считавшего себя последователем «народников», совершивших покушения на царя Александра II, были явные психические отклонения. Необходимо отметить, что незадолго до покушения Николаев был дважды задержан охранниками Кирова, но оба раза отпущен по распоряжению ленинградского НКВД, несмотря на то, что в его портфеле находили заряженный револьвер. Полвека спустя ни один из сотрудников КГБ, с кем Гордиевский обсуждал покушение на Кирова, не сомневался в том, что лично Сталин отдал приказ убить Кирова. Многие считают, что Сталин решил не посвящать в это дело Ягоду, которому не полностью доверял, и действовал через начальника ленинградского НКВД Филиппа Медведя и его заместителя И. Запорожца. Впоследствии Хрущев, по-видимому, ошибочно решил, что Ягода также принимал в этом участие, получив устный приказ от Сталина. Приехав после убийства Кирова в Ленинград, Сталин продемонстрировал свои выдающиеся актерские способности, сыграв самую впечатляющую роль за всю свою жизнь. Медведь встречал Сталина на вокзале, но вместо приветствия он получил неожиданный удар кулаком, затянутым в перчатку. Прямо с вокзала Сталин, переполненный горем, отправился прощаться с телом Кирова. Официально Медведь и Запорожец были уволены с занимаемых ими постов за преступную халатность, но оба продолжали работать в НКВД на Дальнем Востоке вплоть до 1937 года, когда они были расстреляны во время «Великого Террора», как впоследствии предположил Хрущев, для того, чтобы «замести все следы организаторов убийства Кирова».
После убийства Кирова, в тот же вечер вышла директива, требующая немедленного наказания всех тех, кого подозревали в терроризме, вплоть до смертной казни. По словам Хрущева, эта директива вышла «без одобрения Политбюро», по личной инициативе Сталина. Таким образом, НКВД получил власть над жизнью и смертью советских граждан. На протяжении двадцати лет НКВД определял, кто «террорист», а кто нет. Первыми жертвами НКВД, обвиненными в смерти Кирова, были так называемые заговорщики-белогвардейцы, которые проникли в Россию через границу с Польшей, Финляндией и Латвией. 104 вымышленных заговорщика были схвачены и расстреляны. Через три недели после убийства Кирова был раскрыт еще один несуществующий заговор. 22 декабря 1934 года было объявлено, что Николаев принадлежал к подпольной террористической организации, созданной последователями Зиновьева. Сталин лично составил списки двух групп зиновьевцев, которые получили название «Московский центр» и «Ленинградский центр». Позже было объявлено, что Николаев получил пять тысяч рублей от генерального консула Латвии (впоследствии он был выслан из страны), который якобы обеспечивал связь между зиновьевцами и высланным из страны Троцким. 30 декабря было объявлено о том, что после короткого суда без участия защиты все заговорщики были расстреляны. В январе 1935 года Зиновьев и Каменев стали главными действующими лицами первого политического процесса над бывшими лидерами оппозиции. Оба они согласились с расплывчатыми обвинительными формулировками, указывающими на их политическую ответственность за убийство Кирова, граничащую с подстрекательством. Суд приговорил Зиновьева к десяти, а Каменева к пяти годам тюремного заключения. Несмотря на всю абсурдность этого процесса, советские люди отнеслись к нему вполне серьезно, поскольку к этому времени уже успели привыкнуть к разоблачениям различного рода заговоров и подпольных организаций. После завершения процесса Сталин вызвал к себе Ягоду и сказал ему: «Плохо работаете, Генрих Григорьевич!» Он считал, что Зиновьева и Каменева следовало пытать до тех пор, пока они во всем не признались бы. Ягода был настолько потрясен, что не смог сдержаться и расплакался, когда пересказывал этот разговор своему заместителю Георгию Прокофьеву.
В 1935 году Сталин заложил основу для очередного, еще более массированного наступления на существующую и потенциальную оппозицию его режиму. Чистка в партии, начатая в 1933 году и продолжавшаяся в течение всего 1934 года, была в основном направлена на искоренение коррупции и халатности. В 1935 году чистки усилились и стали носить более политизированный характер. Сталин заявлял, что «злодейское убийство товарища Кирова» выявило «много подозрительных элементов в партии». Только хорошо отлаженный карательный аппарат мог их уничтожить, поскольку, как говорил один партийный деятель, «обман, политическое иезуитство и двуличие являются основной тактикой врагов партии». Во всех партийных организациях на местах развернулась кампания самокритики и признаний. По словам Евгении Гинзбург, «большие, набитые людьми залы превращались в исповедальни.» «Каждый такой митинг имел свое собственное меню. Люди каялись в неправильном понимании перманентной революции и в том, что воздержались при голосовании по вопросу о платформе оппозиции в 1932 году. Они признавались в „проявлениях“ великодержавного шовинизма» и в недооценке значения второго пятилетнего плана. Они раскаивались в том, что поддерживали связь с «грешниками» и испытывали слепую привязанность к театру Мейерхольда».
Сталина все больше волновал его главный противник, находящийся вне пределов его досягаемости, Лев Троцкий. Пытаясь добиться признания в совершении политических преступлений, следователи НКВД во время допросов всегда задавали один и тот же вопрос: «Вы согласны или нет с тем, что Троцкий является вождем авангарда буржуазной контрреволюции?» Большинство тех, кого исключали из партии, называли троцкистами и зиновьевцами. Для Троцкого, находившегося в изгнании, это был хороший знак. В январе 1936 года он писал: «Среди десяти-двадцати тысяч троцкистов, исключенных за последние месяцы, есть не более нескольких десятков, возможно, сотен человек из старшего поколения оппозиционеров образца 1923—1928 годов. Основная масса состоит из новобранцев… Можно с уверенностью сказать, что несмотря на 13 лет неслыханных по своей дикости и жестокости травли, клеветы и преследований, несмотря на пораженчество и предательство, которые более опасны, чем само преследование, (троцкистский) IV Интернационал уже сегодня имеет в СССР свой самый сильный, самый многочисленный и самый сплоченный отряд.»
И Сталин, и Троцкий жили в вымышленном ими мире, постоянно подпитывая фантазии друг друга. Вера Сталина в опасность в большинстве своем несуществовавших уже в Советской России троцкистов заражала Троцкого, который не мог не радоваться существованию этих вымышленных последователей, что, в свою очередь, убеждало Сталина в том, что троцкизм представляет собой еще большую угрозу, чем он предполагал.
Почему, однако, троцкисты исчезли из виду в Советском Союзе? Ответ на этот вопрос чрезвычайно прост: ведь, за очень редким исключением, их действительно там не осталось. Однако Сталин и большинство сотрудников НКВД считали, что их исчезновение лишь подтверждает тот факт, что они ушли в подполье, зачастую выдавая себя за преданных членов партии. Летом 1936 года Центральный Комитет по инициативе Сталина одобрил секретную резолюцию, которая давала чрезвычайные полномочия НКВД для уничтожения всех «врагов народа». В июле от имени Политбюро, но скорее всего, по личному указанию Сталина, во все партийные организации был разослан секретный циркуляр: