“起初我以为我在莫斯科党内的提升，是应该感谢卡冈诺维奇的，但我很快就发现，我的提升出于斯大林本人的成分比卡冈诺维奇更多。显然，斯大林一直在通过他的妻子，娜杰日达·谢尔盖耶夫娜注意着我。她在斯大林面前为我唱赞美诗，于是斯大林就叫卡冈诺维奇帮我的忙。”
1930年，赫鲁晓夫当选为莫斯科工业学院党委书记。次年被选为莫斯科市鲍曼区党委书记，后又提升为莫斯科最大的红色普列斯尼亚区党委书记，因在工业领域首倡“斯大林接力赛”，受到斯大林的特别注目和党中央的格外重视。
1932年斯大林妻子娜佳开枪自杀，引起诸多猜测。赫鲁晓夫被提升为莫斯科市委第二书记，成为该市党委第一书记卡冈诺维奇的得力助手。次年，他与卡冈诺维奇一起带头称斯大林为“我们的导师和领导人”，并第一个称斯大林为“天才的领袖”。1934年，联共（布）十七大召开，他是大会发言中唯一的一个称颂斯大林为“天才的领袖”之人，被选为中央委员，时年40岁。所以追根溯源，对斯大林搞个人崇拜的发明权，还属于赫鲁晓夫。
赫鲁晓夫尝到了歌颂斯大林和对斯大林搞个人崇拜的“甜头”，于是，把这当作升官发财的“法宝”和向上爬的“阶梯”，“歌颂”的调门越来越高，“崇拜”的程度愈来愈强，以致使斯大林这样伟大的马克思主义者，也禁不住堕入“迷魂阵”，时不时昏昏然起来。后来，赫鲁晓夫竟然称颂斯大林为“人民的慈父”，“生身的父亲”。1935年2月1日，联共（布）中央全会决定修改1924年苏联宪法，成立了由31人组成的宪法起草委员会，斯大林任主席，布哈林、拉狄克等人也参加委员会的工作。在1936年11月的苏维埃第八次非常代表大会上，斯大林作了题为《论苏联宪法草案》的报告，大会通过了这部宪法的最后文本。赫鲁晓夫也趁此歌颂斯大林，搞个人崇拜。
在大会讨论期间，赫鲁晓夫坚决主张把行将通过的新宪法称为“斯大林宪法”。
他说：“这部宪法从头到尾都是斯大林同志起草的。”据历史档案记载：“宪法起草委员会的文件有力地说明，苏联宪法草案是由一批（党和政府）领导人员集体草拟的。”
在大清洗的日子里，斯大林的肃反扩大化浪高一尺，赫鲁晓夫对斯大林的颂扬风就高过一丈。1936年8月，季诺维也夫、加米涅夫等16人被处死刑的前两天，赫鲁晓夫一方面指示有关部门准备声讨“人民的敌人”的大型集会；另一方面，又组织党的积极分子上书斯大林，坚决支持处决“人民的敌人”。他在群众大会上演说道：“是您，斯大林同志，在全世界高举马克思主义——列宁主义的伟大旗帜，向前挺进，我们向您保证：更紧密地把党和非党的布尔什维克团结在斯大林主义的中央委员会和伟大的斯大林周围。”
请注意，在这里，他又提出了“斯大林主义”！这表明，是赫鲁晓夫第一次把斯大林提到与马克思、恩格斯、列宁等同的高度上。据美国专家拉扎尔·皮斯特腊克考证，赫鲁晓夫的阿谀奉承是空前的，早于联共（布）中央机关报。《真理报》在1934年1月的一篇社论中，只是把“天才的领袖”、“列宁主义”这样的字眼用于马克思、恩格斯和列宁；对于斯大林只是说“无产阶级已经为他们找到一位最称职的继承人——伟大的斯大林，革命思想和革命行动的巨人。”该文还称斯大林为“党的领袖、国际革命坚韧不拔的指导者，世界上第一次社会主义革命的伟大设计师”。但是《真理报》并没有把斯大林称为“天才的领袖”，更没有提出“斯大林主义”。
过了不久，赫鲁晓夫把“斯大林主义”吹得更响了。他说：“我们的宪法就是在地球上六分之一的土地上取得胜利的马克思主义——列宁主义——斯大林主义。我们毫不怀疑，马克思主义——列宁主义——斯大林主义终将征服全球……我们通过我们的宪法，我们庆祝马克思主义——列宁主义——斯大林主义的胜利。”
显然，这种过分“冒调”的吹捧，导出了严重的错误，可能也引起了斯大林的不安。后来，《乌克兰共产党人》杂志在驳斥帝国主义宣传机关的臆造时，曾严肃地指出：
“作为一种学说或社会制度，从来不存在什么‘斯大林主义’，‘斯大林主义’是帝国主义宣传机关所发明的，目的是用来反对马克思主义——列宁主义和国际共产主义运动，特别是用来修正无产阶级国际主义原则的。”
读史至此，禁不住令人拍案惊叹：历史居然如此相似！40年后，在中国，大阴谋家林彪对毛泽东几乎采用了同样的手法——说毛泽东是当代“最伟大的马克思列宁主义者”，他把马克思列宁主义发展到了“顶峰”，他的话“一句顶一万句”！毛泽东闻讯，引起警觉，批判了林彪的“顶峰论”，说“什么一句顶一万句，我的话他根本不听”，“一句连一句也不顶”！暂时刹住了林彪的“吹捧风”。在苏联那“大清洗”加“大吹捧”的日子里，赫鲁晓夫的“高调吹捧”，若没有斯大林的授意反对和驳斥，是没有人敢出来反对或驳斥的，更没有人敢把赫鲁晓夫——时任莫斯科市委和州委第一书记、斯大林的红人创造的“斯大林主义”，斥之为“帝国主义宣传机关所发明的”。如果没有斯大林的授意或支持，即使有人敢出面反对，也必然会成为当时“大清洗”和“大屠杀”的对象。然而没有。这使人不能不对赫鲁晓夫说斯大林从来不制止颂扬他，为了“抬高自己的威望”，“采取了一切可以想到的方式”产生质疑。
1937年1月23日至30日，莫斯科公开审讯“托洛斯基平行总部”案件，以“背叛祖国”等罪名，将皮达可夫等13人判处死刑，拉狄克等4人处以十年监禁，推动了第二次肃反扩大化的恶浪。对此，赫鲁晓夫呼风唤雨，推波助澜，起了非常重要的宣传、组织作用。1月30日，他亲自组织了20万人在红场举行大会，支持对皮达可夫等托洛斯基分子的判决，声讨被告的“罪行”。在大会上，赫鲁晓夫发表了重要演说，并通过广播、报纸，传往全国。赫鲁晓夫说：“这些凶手瞄准了我们党的心脏和大脑。他们攻击斯大林同志就是攻击我们全体，攻击工人阶级，攻击劳动人民！他们攻击斯大林同志就是攻击马克思、恩格斯和列宁的学说！”“他们攻击斯大林同志，也就是攻击人类所拥有的一切美好的东西，因为斯大林就是希望，就是期待，就是全体人民进步的灯塔。斯大林是我们的旗帜，斯大林是我们的意志，斯大林是我们的胜利。”
这时候，赫鲁晓夫已经把歌颂斯大林和声讨“受到迫害的人们”紧密地结合起来，用“忠实的男女同志”的头颅，铺垫他向上爬的阶梯。斯大林的肃反扩大化，成了赫鲁晓夫之流晋升、腾飞、飞黄腾达的翅膀。
1938年3月2日至13日，苏联最高法院军事法庭对“右派和托派反苏联盟”案件进行审理。这是肃反运动中的第三次公开审讯。主要被告是布哈林、李可夫和克列斯廷斯基等21名过去的苏联领导人。布哈林是党的杰出理论家，是“斯大林宪法”的主要起草人，时任苏联政府机关报《消息报》主编。列宁曾称他为“党的宠儿”，但也说他形同软蜡，政治上不稳定。布哈林对于罗织的罪名大声怒斥，但无济于事，他和李可夫等19人被处以死刑。
赫鲁晓夫对布哈林、李可夫等人比较了解，也曾作过不少的赞颂，然而此时，他却翻脸不认人，在一系列的会议上，从十多人的领导人员会议到十万人以上的群众大会上，都反复强调：肃清“人民的敌人”——卑鄙的托洛斯基分子、季诺维也夫分子、布哈林分子、李可夫分子——这些***走狗、祖国的叛徒，都是“人民的慈父”斯大林同志的英明、洞察力和无穷无尽精力的伟大胜利。一次，在莫斯科斯大林选区8万人的群众大会上，赫鲁晓夫说：我们的敌人还没有被彻底粉碎，他们还隐在黑暗的角落和巢穴里。因此，他号召要坚定地、无情地粉碎工人阶级的敌人——托洛斯基分子、布哈林分子以及其他垃圾，其他坏蛋。他说只有这样，才能表明莫斯科人对列宁——斯大林的党，对伟大的斯大林衷心的热爱。
赫鲁晓夫的阴谋得逞了。1938年初，斯大林提议由赫鲁晓夫担任乌克兰共和国党中央委员会第一书记。原来，乌克兰党中央第一书记科西奥尔和乌克兰人民委员会主席丘巴尔，都曾是赫鲁晓夫的老领导。他们对赫鲁晓夫成长、晋升都曾有过贡献，也曾受到赫鲁晓夫的敬重。但到此时，赫鲁晓夫一朝权在手，翻脸不认人，指责他们在肃反问题上有“温情主义”，对敌斗争不力。1939年2月，科西奥尔和丘巴尔先后被处死。对此，斯大林当然负有领导责任；然而，时任乌克兰党中央第一书记，并给斯大林提供重要情况的赫鲁晓夫，不能说与己无关。不仅如此，赫鲁晓夫到乌克兰后的半年内，还把科西奥尔和丘巴尔留下的并经大清洗幸存下来的83人，推进了大恐怖浪潮的深渊，其中有不少人都是赫鲁晓夫过去的同事、朋友。1938年5月，赫鲁晓夫公开宣布：“许多坏蛋、变节者和叛徒钻进了基辅的党组织。他们是外国的间谍。我们必须记住这一点，以便动员起来，更加团结一致；以便我们有力地打击工人阶级的敌人，打击托洛斯基分子、布哈林分子、民族主义分子。我们必须铲除一切垃圾，好让社会主义在我们的土地上繁荣昌盛起来。”赫鲁晓夫的两面手法着实厉害：一方面，对斯大林和上司吹捧、歌颂，搞个人崇拜，为他的向上爬找“提携人”；另一方面，利用肃反扩大化，大搞清洗、镇压和恐怖活动，把一切可能妨碍他“晋升”的人，包括他过去的领导、同事、朋友，都戴上“外国间谍”、“***特务”、“托洛斯基分子”、“布哈林分子”等帽子，“统统抓起来，加以消灭”，使一般人不敢对他冒犯。所以，他向上爬的速度特别快。1938年，他经斯大林提议，任乌克兰共和国中央第一书记，兼任基辅州和基辅市委第一书记。不久，又被选为苏联最高苏维埃主席团委员，联共（布）中央政治局候补委员，成为苏联党政10位主要领导人之一。1949年12月，赫鲁晓夫被调回莫斯科，任莫斯科市和州的第一书记，兼任联共（布）中央书记处书记。1952年在联共（布）十九大上，赫鲁晓夫作了关于修改党章的报告，被选入主席团常务委员会，成为苏共5位主要领导人之一。
斯大林没有指定接班人。他逝世后，马林科夫虽被任命为党中央书记、部长会议主席，但他在政治上相当软弱，缺乏战略决策能力。赫鲁晓夫和贝利亚窥测方向，伺机夺权。贝利亚企图通过内务部、克格勃来驾驭马林科夫，经过军事政变的方式统掌苏联大权；赫鲁晓夫则用软办法，利用自己在党内的影响，通过重新恢复党的权威来掌权。他上下串联，多方活动，取得了马林科夫等人的支持，又征得了朱可夫等将帅的鼎力相助，苏共中央主席团一举粉碎了贝利亚集团，当场逮捕并处决了贝利亚。1953年9月，赫鲁晓夫取得了苏共中央第一书记的职务。
1956年2月，赫鲁晓夫在苏共二十大上作的秘密报告，揭露了斯大林晚年的错误，特别是揭露了斯大林在三十年代搞肃反扩大化、践踏社会主义民主和法制的内幕，揭露了斯大林搞个人崇拜以及在卫国战争初期由于缺乏警惕造成巨大损失的有关材料。这份“秘密报告”，犹如一颗巨型的原子弹在克里姆林宫爆炸，它造成的“冲击波”迅速地辐射到苏联全国，辐射到全世界，令国内外公众震惊。
赫鲁晓夫说在苏共第十七次代表大会的时候，他就是代表。在大会接近尾声时，一批州委书记利用会议休息时间，推开了主席团房间的门，找到基洛夫，要求基洛夫向斯大林转达意见，说大家对他的粗暴、急躁和傲慢都有意见，希望斯大林能够注意。基洛夫摇摇头，不想转达，要他们自己对斯大林当面去说。州委书记们说基洛夫和斯大林是朋友，说话容易接受。正在这时，斯大林来了，基洛夫顺便把州委书记们的意见告诉了斯大林。
斯大林当时回答说：“谢谢你，谢尔盖。你是真正的朋友，我不会忘记这一点。”在场的人都很高兴。但在代表大会选举时，有数百名代表从无记名投票的名单上，勾掉了斯大林的名字。
赫鲁晓夫认为，斯大林对此耿耿于怀，并且把猜疑心化作了报复行动。对代表们采取了残酷的打击报复措施。他列举的事实是：代表大会的1966名代表中有1108名不久就被处决了；138名中央委员和中央候补委员中有98名在被处决的名单之列。