赫鲁晓夫1964年下台。苏共政治局（主席团重新变成了政治局）推翻了赫鲁晓夫在国内外实施的诸多政策，政治局也掩盖了不同意见的争论。但这是对赫鲁晓夫政策的修正，不是要回到真正的斯大林主义。新的苏共中央总书记勃列日涅夫（LeonidBrezhnev）从没考虑过实施恐怖统治或个人专制。“稳定干部”成了一句口号。但实际上苏共政治局在1969年斯大林生日这一天打算重新评估斯大林的遗产。《真理报》的社论准备了一份赞美词，只是在最后一分钟由于意大利和法国共产党的干预才没能公开发表。（但这也迟了，蒙古共产党已经印发出去了，因为乌兰巴托的时区要早一些。）
但重评斯大林的动机还在。1984年7月，戈尔巴乔夫（MikhailGorbachev）上台前，政治局考虑过这个问题。年长的政治局成员对斯大林还是有感情的，对赫鲁晓夫很不满：
尤斯蒂诺夫（Ustinov）：在评价赫鲁晓夫行为的问题上，我想谈谈我的观点。他带给我们太多的伤害。想想他对我们的历史，对斯大林都做了些什么。
葛罗米柯（Gromyko）：他击垮了苏联在世界其他国家眼里的良好形象。
吉洪诺夫（Tikhonov）：那赫鲁晓夫为我们的经济做了什么呢？我自己不得不在一个全国经济地区委员会那里工作！
戈尔巴乔夫：他对我们党所做的就是把党分成了工业党和农业党！
尤斯蒂诺夫：我们一直反对全国经济委员会。正如你们所回忆的，中央委员会中政治局的多数成员都反对过赫鲁晓夫。在纪念反法西斯战争胜利十四周年时，我就提出要讨论一个问题：难道不应该把伏尔加格勒重新改为斯大林格勒吗？数百万人将会接受改名的。[10]
斯大林死时，尤斯蒂诺夫是国防部长，葛罗米柯一直是驻联合国大使，吉洪诺夫是冶金部长。
为斯大林恢复名誉的想法不了了之，因为戈尔巴乔夫在1985年担任党的总书记后，他在政治局不再提这件事了。很快斯大林又成为批判的对象。在戈尔巴乔夫的公开性原则下，斯大林滥用权力的许多材料被揭发出来了。斯大林建立的行政命令制备受指责。电影、小说、诗歌以及历史著作都在指责斯大林。戈尔巴乔夫通过知识分子的著书立说让公众明白，全面评估斯大林的遗产对苏联社会的新生是十分重要的。但这一过程有点失控，因为有些批评斯大林的人认为列宁对权力滥用也负有责任。他们将行政命令制的起源追溯到苏联成立的时候。但在公开讨论中，也有人赞扬斯大林，有人还是肯定了斯大林在20世纪30年代苏联工业化以及反法西斯战争胜利中做出的贡献。
但事情还没结束。戈尔巴乔夫指责斯大林是历史上最大的罪犯。1991年苏联解体，俄罗斯联邦成立后，鲍里斯·叶利钦（BorisYeltsin）还在批判斯大林，与戈尔巴乔夫不同的是，他既批判斯大林，也批判列宁。批判一直持续到2000年普京当选俄罗斯总统。普京的祖父曾做过列宁和斯大林的厨师。普京总统不想听20世纪三四十年代权力滥用的故事，相反他希望能够宣扬那些年代苏联所取得的成就。[11]普京不赞同诋毁历史，他象征性地恢复了苏联的国歌，当然是换了歌词了。他经常提及他在克格勃（KGB）工作的经历，克格勃的前身就是斯大林时期的安全保卫部门。[12]为斯大林恢复名誉显然不是普京的目的，他是要说明俄罗斯帝国、苏联、俄罗斯联邦是一脉相承的。自20世纪80年代后期以来，斯大林第一次不再成为批判的对象。普京认为斯大林就是一个历史人物，他的是非功过让学者们去评说就可以了。这对于长眠于地下的斯大林来说是一种侮辱。只要他死后还被人们批判，他在莫斯科的政治中就仍是一个活生生的人物。普京上台后，斯大林成了被官方忽视的人物。
但社会没有忘记他。尽管人们揭露他的独裁，但还是怀念斯大林和他统治的那个时代。2000年的民意测验证实了这一点。当被问及20世纪哪个时期最让他们难忘时，大多数受访者认为是勃列日涅夫时期，30％的人认为是赫鲁晓夫时期，28％的人认为是革命时期，18％的人认为是尼古拉二世统治时期，而有26％的人认为是斯大林统治时期，这一数字不算是最低的。不赞成斯大林统治时期的人则高达48％，但事实上，有1/4的人并不反对斯大林的统治，这令那些主张变革社会观念的人很失望。[13]并不是每个人都对历史有美好的回忆。每到斯大林逝世纪念日时，有的家庭会为“美国医生”薛尼－斯托克司的健康庆贺。他们想起了1953年3月斯大林在孔策沃别墅得了要命的呼吸系统疾病。（事实上确实有两位医生，薛尼和斯托克司，但他们不是美国人，而是爱尔兰人。）[14]实际上，成百万的苏联公民经常会想起那些毁誉参半的政治家。