在校期間赫魯曉夫認識了斯大林的妻子，他在回憶錄中稱他為自己“幸運的彩票”，認為她會在斯大林前提自己的表現。有人認為他地位尚低，起關鍵作用的是卡岡諾維奇。1930年他成為克拉斯諾普雷斯奈斯區黨委書記；兩年後他任莫斯科黨組織在卡岡諾維奇身後的第二書記；1934年他任莫斯科黨組織領導並入選蘇共中央委員會。期間，他全力修建莫斯科地鐵。他曾要求工人連續幹48小時，無視技術人員的警告，結果發生事故，這些事僅作為為偉大事業服務的英雄主義事跡記錄。盡管地建未能按期建成，他仍被授予列寧勳章。1935年他任莫斯科州州委書記。
1934年，斯大林發起大清洗，赫魯曉夫鼓吹斯大林路線。在審判期間他要求處死委諾維也夫和加米涅夫。他還協助抓捕消滅自己的同事和朋友。在莫斯科市委和省黨委的38名官員僅3人幸存。在莫斯科的其他地區的146名黨委書記有136人被捕。他的回憶錄中說“幾乎和他一起工作的人都遭到了逮捕。”清洗行動由赫魯曉夫簽發逮捕令，而他很少幫助他的朋友和同事，甚至什麼都沒做。1937年6月27日，政治局確定在莫斯科州抓捕3.5萬“敵人”的定額，其中約5000將被槍決。
赫魯曉夫要求消滅莫斯科的富農，以完成部分定額。7月10日，他向期大林報告說已逮捕約41304名“”罪犯與富農分子”，1938年——1940年被捕人數進一步上漲。烏克蘭共產黨政治局和書記處除一人外都被逮捕。赫魯曉夫也發現了問題，並在烏共十四大上提出這一問題。
1939年8月，《蘇德互不侵犯條約》簽訂，9月1日德國閃擊波蘭，17日蘇軍發起攻擊，赫魯曉夫隨軍入境。占領區的烏克蘭裔因遭波蘭當局壓迫對蘇軍熱烈歡迎，希望蘇聯支持他們民族獨立。赫魯曉夫為讓西烏克蘭“自願”加入蘇聯，他們組織會議、遊行和示威，甚至在投票中作弊。他解散烏克蘭的教育、宗教機構，逮捕有影響的知識分子。11月1日，西烏克蘭加入蘇聯。赫魯曉夫用東烏克蘭官員管理西烏克蘭組織，推行農業集體化等政策使當地民怨沸騰。
1941年6月22日德國入侵蘇聯，赫魯曉夫正在基輔。斯大林任命他為政治委員，沒有他的簽署不能發布任何命令。斯大林令西南方麵軍死守基輔，但紅軍遭德軍圍殲，赫魯曉夫和少數將領逃走。德國稱他們俘獲六十五萬五千餘名俘虜，蘇聯統計的數據則少十二萬左右。朱可夫在回憶中稱，他在戰前曾勸斯大林撤退，但斯大林被赫魯曉夫影響。赫魯曉夫在回憶錄中說他與布瓊尼決定調兵以防德軍包圍，直到鐵木辛哥從中央趕來接替布瓊尼。他稱堅守基輔不是自己的意見。