1934年12月1日傍晚，聯共中央政治局委員、列寧格勒州委書記基洛夫在列寧格勒州委機關所在地斯莫爾尼宮內被槍殺。基洛夫事件撲朔迷離，至今仍是歷史懸案。兇手尼古拉耶夫是內務人民委員會工作人員，曾被開除黨籍。案發後他當場被捕，當天晚上，史太林等中央領導人趕到出事地點，親自審問，但審訊記錄始終沒有公佈，而尼古拉耶夫當月即被槍決。無論基洛夫案的真相如何，這事件給史太林提供了徹底清洗反對派、以至潛在對手的機會，歷時四年之久的大肅反運動正式開始。

基洛夫被暗殺的當天，史太林在沒有經過政治局討論和批准的情況下，對國家刑法作了如下修改：
1. 各司法機關應加速審理被控告犯有策劃或採取恐怖行動的罪行的犯人。偵察恐怖活動案件不得超過十天。
2. 蘇聯中央執行委員會主席團不會考慮這類罪犯要求赦免的申請。判決一經作出，不得上訴，不得赦免。
3. 內務人民委員會應在這類罪犯被判處死刑以後立即予以執行。

以上條文被稱為「基洛夫法」，它為大規模的肅反運動提供了法律依據。

在整場肅反運動中，赫魯曉夫的態度就如美國學者威廉·陶布曼在《赫魯曉夫：他和他的時代》一書中寫道：「在大清洗運動中，赫魯曉夫始終站在史太林一邊。」他在莫斯科時期，38名市、區高級官員中只有3人倖存，146名黨委書記中有10人倖存，63名當選的莫斯科黨委成員中有8人倖存。1937年政治局分配給他逮捕35000名「人民公敵」的名額，其中5000人要處決。而赫魯曉夫向聯共中央報告，逮捕了41000人，處決8500人。後來赫魯曉夫在回憶錄中也說：「幾乎所有和我一起工作的人都遭到了逮捕。」赫魯曉夫本身在大清洗之初，亦因為他早年與托洛斯基主義的關係而遇上麻煩，後來在卡岡諾維奇的說項下，史太林接見了赫魯曉夫，並在莫洛托夫的建議下，赫魯曉夫公開供認了自己曾經的犯罪行為，並補充說史太林「知道我犯的錯誤」，結果他的「坦白」贏得了史太林的認同，並立即被重新選入黨委。

由於大清洗的浪潮使烏克蘭黨組織遭到嚴重破壞，到1937年12月，史太林需派一個信任的人，去領導和控制烏克蘭，最終他選中了赫魯曉夫。1938年6月，烏克蘭共產黨第十四次代表大會例行選舉新的中央委員會和政治局，赫魯曉夫正式當選為烏克蘭共產黨中央委員會第一書記和基輔州委第一書記。