尽管对地下铁道一无所知（也许正是因为此），然而赫鲁晓夫还是不顾一切地承担起了巨大的风险。他和莫斯科市长尼古拉·布尔加宁（Nikolai Bulganin）无情地驱使着七万多名工人没日没夜地工作着。有一次，他们要求工人不间断地连续工作了48个小时，并无视工程技术人员提出的隧道或者隧道上面的建筑物可能坍塌的警告。终于，可怕的事故发生了，其中有地下火灾与灌水，但是在关于地铁项目充满狂热的记录里，这些事故只是为伟大事业服务的英雄主义事迹而已。
在地铁项目建造期间，赫鲁晓夫和他的下属一样，也是拼命地工作。“虽然我的正式工作是在市委员会里，”他回忆说：“但80%的时间都投入到了地铁工程中。我总是从竖井里去莫斯科委员会上下班，早上我从离我居住的地方不远的竖井下到隧道里，然后再从离市委办公大楼不远的竖井爬出来。我很难描述当时我的一个工作日有多紧张。我们都是尽量少睡觉，这样我们就能将所有的时间都投入到我们的事业中去了。”
地铁工程没有在1934年11月的最后期限全部完工。但是1935年5月1日当第一列火车从索科尔尼基开向库尔图里公园、从科明图恩大街（后来的加里宁斯卡娅大街）开向基辅车站时，赫鲁晓夫就在车上，与卡冈诺维奇一起享受了这项宏大工程所带来的荣耀，莫斯科地铁工程以卡冈诺维奇的名字命名。一位地铁工程师这样写道：“在人的一生中，有一些特别值得纪念的日子。在这样的日子里，他会突然开始用一种全新的方式来思考他很长时间以来一直认为自己知道的所有简单的事情。在这样的日子里，他会对以前认为很当然的事情与现象充满爱意。赫鲁晓夫同志和我谈话的那天就属于这样的日子。”
因为在地铁建设工程以及在一个以他的名字命名的制造精密电子设备的工厂建设中所起的作用，赫鲁晓夫获得了他向往已久的列宁勋章，他还因此成为莫斯科省的第一书记。他对所有这些荣誉的感激之情又是怎样的呢？“列宁勋章设立于1930年，”赫鲁晓夫记得：“我想我是第110位获此殊荣的人。这就是说，在五年的时间里，总共只有110人获得过列宁勋章。这说明了它在人们心目中的崇高威望。我觉得就应该如此：奖励中所包含的荣誉和价值越高越好。后来，列宁勋章开始被更加普遍地授予了，从而也就失去了它的重要意义。”
1935年赫鲁晓夫成为了苏联新闻短片的主角，这种权力与权威的感觉与他1932年时的惴惴不安形成了鲜明的对比。一个短片记录了他视察一座通往基辅地铁站的新莫斯科河流大桥时的情景。赫鲁晓夫乘坐的是一辆宽大的黑色轿车，身后跟着一大帮随从。他戴着鸭舌帽，身穿长长的黑色大衣（身后紧紧地跟着保卫人员），向列队的工人们挥手致意。他爽朗地笑着，然后与大家一一握手。由于他到来的时候正赶上惯常的吸烟休息时间，因此画面上的所有人不是手上夹着，就是嘴里含着香烟——除了自我克制的赫鲁晓夫以外。他坚定地走过大桥，不时地对着左右发号施令，然后钻进他的黑色轿车里，扬长而去，后面是几辆其他的黑色轿车。
在他离开前，摄像机聚焦在他的双眼上。赫鲁晓夫的双眼显得特别明亮，具有穿透力，正完全专注于所看到的一切。这双眼睛也给谢尔盖·赫鲁晓夫一个儿时的朋友留下了深刻的印象，他是在20世纪50年代第一次见到谢尔盖的父亲的。这位朋友对赫鲁晓夫其貌不扬的外表与他双眼里流露出来的炽热情感之间的反差感到很吃惊。“如果你想了解赫鲁晓夫是如何成为如此一个强力人物的，你只要看看他的眼睛就明白了。”
另一个1935年的新闻短片记录了赫鲁晓夫视察莫斯科第12幼儿园时的情况，这个幼儿园也是以他的名字命名的。当赫鲁晓夫和他的随从们到达时，所有的东西都被放置得井井有条，孩子们穿着漂亮的衣服，正在喝茶。他和他所有的随从都穿着白色的工作服，他里面是一件深色的衣服，其他人好像都穿着制服。赫鲁晓夫检查了一张小椅子，将椅子翻转在手上，看看是如何制造的，然后看了一双很小的童鞋。当他挥手告别时，那张和善的城市父母官的脸上露出了颇具感染力的微笑。他的微笑也同样征服了一家电灯工厂工人的心，赫鲁晓夫在那里对党的积极分子发表了一次演讲。身穿斯大林风格的短袖束腰大衣，双手像乐队指挥似的不停地挥舞着，赫鲁晓夫在公开场合显得完全的放松。在演讲过程中，他不时地与听众进行着非正式的交流，很显然他对自己巧妙的回答颇感得意。
当然，并不是所有的事情都很顺利。早在30年代中期，赫鲁晓夫太快作出决策与喜欢走极端的倾向就给他带来过麻烦。他驱使斯塔汉诺维特工人超额完成定额的做法就遭到了上级的批评，谴责这是“盲目追求记录”的做法。1934年，有人给赫鲁晓夫捎了一个口信，让他给一个电话号码回电话，他想起这是斯大林家里的电话。斯大林和他谈了关于公共厕所的问题。“显然人们到处寻找，却找不到地方大小便。”斯大林说：“这样下去不行。这种状况使市民们很狼狈。你和布尔加宁商量一下，采取措施改善这种状况。”[16]
虽然赫鲁晓夫不是拆除莫斯科旧房屋的主要推动者，但他也没有反对。“我们砍倒树木，”他在1937年一次中央委员会全体会议上说：“为的是重建莫斯科，这样莫斯科将成为真正的首都，而不是一个村庄，为的是结束人们认为莫斯科只是座大村庄的看法。”
“一些布尔什维克流下了眼泪，”他在1937年一次市党员大会上说：“‘看看你们正在推倒的是什么！’他们说。但是我要说的是，当他们为此流下眼泪时，他们就像樱桃园里的主人翁。……我们不能以整个城市的利益为代价去迁就那些生活在小片土地上的人。”
斯大林对他的莫斯科下属拆毁旧房屋的做法给予了鼓励，但是当听到人们的抱怨时，他还是对他们进行了批评。一天，著名的飞机设计师亚历山大·S.雅科夫列夫（Aleksandr S.Yakovlev）在与斯大林办完公事后逗留了一会儿，两人闲聊了起来。斯大林问现在莫斯科市民都在谈论些什么，由于看到他心情不错，雅科夫列夫才敢说人们对大面积毁坏莫斯科的绿地感到不满，因为斯大林“不喜欢树木”。斯大林告诉雅科夫列夫，他批评过赫鲁晓夫与布尔加宁，他曾经向他们指出过一些不起眼的灌木丛。“我告诉他们……这种绿化是不需要的。但是赫鲁晓夫与布尔加宁用他们自己的方式理解了我的意思，他们的做法正应了一句老话‘你让一个傻子去做祈祷，他就会在地上磕破额头。’”
“是这样吗，莫洛托夫？”斯大林问站在旁边的总理：“不管他们做什么，到头来受批评的总是我们。”
在1934年第十七届党代表大会后，斯大林这位独裁者不久便开始了对那些敢于反对他的人的秋后算账，赫鲁晓夫在这次大会上发表了一次称赞“我们的天才领袖斯大林同志”的发言，并将“莫斯科党组织建立在纪律与思想基础上的团结归功于拉扎尔·莫伊谢耶维奇·卡冈诺维奇卓越的忘我领导才能”。1934年12月1日，基洛夫在列宁格勒被处决。[17]其后斯大林很显然在没有与全体政治局成员协商的情况下颁布了一项法令，加快了对宣称与恐怖主义行为有关之人的处理程序，他下令只要涉及类似案件，可以“立即”处以死刑。根据这项法令，数十起与基洛夫谋杀没有任何关系的“反革命罪犯”被很快审判，并立即执行了死刑。1935年1月，中央委员会的一封秘密信件呼吁党组织清除所有隐藏在党内的反动派。接下来是一阵逮捕浪潮，这就是后来在劳改营里为人们所熟知的“基洛夫风潮”。数以万计的人（主要是原来的无政府主义者、商人以及公务员和他们的家人，但是也有工人和农民）被驱逐出列宁格勒，也有一少部分人被驱逐出莫斯科。1935年莫斯科进行了一次党内清洗，结果接受审查的党员中有7.5%被开除出党，他们很多是原来的机会主义者，但是也有一些则是普通的共产党员。[18]
1935年1月，季诺维耶夫、加米涅夫以及其他17人在莫斯科受到了审判，指控他们组建了一个与基洛夫被杀有关的莫斯科中心。他们当时暂定被处以五到十年徒刑。后来的事实说明，1935年1月至1936年8月这一段时间是风暴之前的平静期。一个主要由布哈林起草、包含有着民主自由与权利所有方面的新苏联宪法颁布了，布哈林认为新宪法中的部分内容也许真的会得以实施。然而与此同时，斯大林却在秘密准备着一个对季诺维耶夫、加米涅夫以及其他被认为是托洛茨基-季诺维耶夫中心的人的新的审判，此次是逼迫他们承认曾经参与策划对斯大林和基洛夫的谋杀。
新的审判于1936年8月19日开始，地点是前诺贝尔俱乐部的蓝白舞厅，即现在商会大楼里的十月厅。主起诉人安德烈·维辛斯基（Andrei Vyshinsky）要求“将这些疯狗处决——一个也不留”。当然，他们一个也没有逃脱被处决的命运，尽管为了得到他们的供认，斯大林曾亲自向季诺维耶夫和加米涅夫承诺，他们的生命以及他们家人和支持者的生命会得到保证。
在审判之前、期间以及其后，赫鲁晓夫都是斯大林路线最起劲的鼓吹者之一。他告诫莫斯科党的工作人员要“以对敌人的痛恨、对反革命托洛茨基-季诺维耶夫分子的痛恨、对右派异端分子的痛恨以及对布尔什维克党的热爱和对我们伟大的领袖和导师斯大林同志的热爱，教育广大群众”。在审判结束前的三天，他要求处死季诺维耶夫与加米涅夫：“任何一个对我们国家所取得的成功、对我党在伟大的斯大林同志领导下所取得的胜利感到欢欣鼓舞的人都会发现，对于这些托洛茨基-季诺维耶夫集团唯利是图的法西斯走狗，我们只有一句话，就是处死他们。”
1937年1月又进行了另一次公开审判。[19]此次赫鲁晓夫在红场面对瑟瑟寒风中的大约20万莫斯科市民发表了一次演讲，呼吁血债血还：“托洛茨基集团只是一帮间谍与唯利是图的刽子手、异端分子与德国和日本法西斯主义的帮凶。卑鄙下流的托洛茨基派的堕落者身上散发着腐败的恶臭。”“犹大式的托洛茨基及其帮派”最卑鄙的罪行是“向斯大林同志伸出了罪恶的手……斯大林同志是人类崇高进步事业的灯塔。斯大林是我们的旗手！斯大林是我们的意志！斯大林就是我们的胜利！”[20]
在斯大林审判以及后来处决布哈林与李可夫前，季诺维耶夫与加米涅夫被逼将两人牵涉到他们的罪行中，两人必须先被驱逐出中央委员会。虽然布哈林和李可夫在1937年2月的一次中央委员会全体会议上试图为自己辩护的声音被压制了下去，但由36名成员组成的决定他们两人命运的委员会发生了意见分歧，一些人赞同先审判后处决（甚至有一部分人认为审判也是多余的），但是还有一些人倾向于从轻发落。[21]赫鲁晓夫在全体会议上的唯一发言只是关于一个无关痛痒的日程问题，为即将到来的选举做准备。在那些阻断布哈林生命之路的人中，赫鲁晓夫算是比较克制的一个，他对审判布哈林和李可夫投了赞成票，但认为不应预先设定死刑。[22]
此时，大清洗的步伐加快了。接下来被整垮的是红军军官们，其中包括像米哈伊尔·图哈切夫斯基元帅（Mikhail Tukhachevsky）这样的天才将军。当希特勒进攻苏联时，人们痛苦地想起了图哈切夫斯基元帅。在陆军与海军副人民委员简·加马尔尼克（Jan Gamarnik）被选举进莫斯科党委委员会前，赫鲁晓夫曾给他做过担保。七天后，当《真理报》揭露加马尔尼克是“托洛茨基分子”时，赫鲁晓夫宣布加马尔尼克的当选证明了“这个敌人对自己进行了罪恶的伪装，从事的阴谋颠覆活动隐藏得很深”。
大批斯大林的亲信在各省的政坛上崛起。只有在安德烈·日丹诺夫（Andrei Zhdanov）的列宁格勒、贝利亚的高加索以及赫鲁晓夫的莫斯科，才是第一书记负责监督清洗工作。尽管让大众普遍憎恨前克里姆林宫的同事是令人厌恶的一件事，但要鼓励因为恐惧而近乎疯狂的普通党员相互指责则是更糟糕的事情。然而，这正是赫鲁晓夫的所作所为。“这不是一场公开的斗争，”他在1937年5月莫斯科市党员大会上警告与会代表们说：“在公开的斗争中，子弹是来自敌人一方。而我们现在所要斗争的对象就坐在你的身边，他们对我们的成功与我们党所取得的成就也会大加称赞，但就在同时他们会偷偷扣动口袋里的扳机，等待时机向你射出罪恶的子弹，就像他们对谢尔盖·米罗诺维奇·基洛夫所做的那样。”对待这种叛徒的办法就是“痛揍他一顿”，然后再“在内务人民委员部揭露出来的无可争辩的证据面前”玩味他的招供词。
“这些恶棍必须被打倒，”赫鲁晓夫在1937年8月发出振聋发聩的声音：“打倒一个、两个，或者十个恶棍，我们就可以为成千上万的人解除隐患。正因为如此，我们的双手坚决不能颤抖，我们必须为了人民的利益从敌人的尸体上碾过。”