史達林在一個抽屜的報紙下面夾著三頁紙，其中一份是狄托寫的：不要派人來殺我了。我們已經抓了五百個人了，有些人帶著炸彈，有些人拿著槍……如果你還是派人來殺我，那我也派個人去莫斯科，我肯定不會送第二個。
1955年6月，來訪的蘇聯領導人尼基塔·赫魯雪夫和尼古拉·布爾加寧與狄托會談
赫魯雪夫在1956年的蘇共二十大上提出了史達林的問題。有人說破壞蘇聯秩序是危險的，他反駁說：「如果我們不在中央全會上說真話，我們在將來的某個時候可能不得不說出真話。那時候我們不是在發表演講，而是在接受人民的調查!」
史達林保留的三封信
1953年3月初，改革浪潮吹遍整個蘇聯。經受了長期的壓制後，史達林的繼任者終於可以在他死後變革其政策。蘇共中央主席團沒有一個人贊同他總體上保守的政策，甚至像莫洛托夫、卡岡諾維奇這樣蘇共黨內的保守派也贊同實施一定程度的改革。史達林長期以來打擊的改革終於有了實施的可能性。然而社會上並未出現關於改革的討論。蘇聯當時是不允許民眾討論這些問題的。蘇共黨內史達林的接班人想做的最後一件事就是要讓蘇聯的普通公民，或者政府的基層官員能對克里姆林宮的決策產生影響。
莫洛托夫和卡岡諾維奇無法阻止馬林科夫、貝利亞和赫魯雪夫的改革計劃。馬林科夫想增加集體農莊的撥款以推動蘇聯的農業生產，他還贊同增加輕工業的投資。赫魯雪夫想在蘇聯開荒，以結束幾十年以來蘇聯糧食供應不足的問題。馬林科夫和貝利亞決心推動蘇美的和平共處：他們擔心冷戰將給人類帶來一場災難。貝利亞希望同南斯拉夫建立友好關係，他也想廢除俄羅斯在蘇聯境內的特權，並減少對各民族文化自我發展的限制。馬林科夫、貝利亞和赫魯雪夫都認為，公眾的生活不應該像史達林時期那樣充滿暴力和專斷。他們主張釋放勞動營里的政治犯並封鎖官方媒體，避免宣傳老一套的做法。如果蘇聯改變了史達林的政策，那麼就沒必要把史達林當神一樣去崇拜了。
蘇共主席團非常謹慎地處理史達林的物質遺產。1924年列寧逝世時，史達林成了列寧著作的管理者，他決定應該出版列寧的哪些著作，哪些不應該出版。他自己出版了《論列寧主義的基礎》。史達林參考列寧的著作，從而為自己的所作所為尋求合法性。史達林的接班人都熟悉這些。1953年3月5日，經蘇共中央委員會授權，他們將《史達林文集》沒收，並匿名送給了各公共圖書館馬克思列寧主義研究所，只留了幾百本書。史達林的許多信件和電報都被燒掉了，他的大部分文章和著作的草稿也不見了。「史達林文集」的最後一部分很不完整。
史達林孔策沃別墅的桌子上還有秘密。在一個抽屜的報紙下面夾著三頁紙。其中一份是狄托寫的：
史達林：
不要派人來殺我了。我們已經抓了五百個人了，有些人帶著炸彈，有些人拿著槍……如果你還是派人來殺我，那我也派個人去莫斯科，我肯定不會送第二個。
這是狄托寫給史達林的。還沒有人敢這樣對史達林說話。也許這就是為什麼史達林留著這個紙條的原因。他還保留著布哈林寫給他的最後信件：「柯巴，為什麼你一定要我死呢?」難道史達林每次重讀這封信時很興奮?(據說他一直對布哈林有看法。)第三份是列寧1922年3月5日寫的一封信，內容是要史達林為自己的粗魯言行向克魯普斯卡婭道歉。這是他收到的列寧的最後一封信，信的內容很傷自尊。如果不是他心裡放不下這幾件事情，他是不會保留這些信件的。
蘇共領導人把這三封信當成機密。但史達林死後他們改變了蘇聯的公共話語，《真理報》讚揚史達林的內容少了。一些發表的文章開始批評「個人崇拜」。雖然這些文章大篇引用史達林著作中的話，但並不是說史達林的個人崇拜是歷史上最冠冕堂皇的。蘇共中央主席團討論新政策時，由於貝利亞搜集到了史達林與警察部門談話的錄音，所以貝利亞重新擔任內務部部長。錄音顯示，史達林打算將恐怖進行到底。貝利亞讓中央委員會的成員讀讀錄音記錄。
改革者面臨一種困境：如果他們宣布放棄史達林的遺產，那他們統治的合法性將會大打折扣，但如果他們不馬上實施改革，社會的不滿會積聚，他們也會有麻煩。還有更大的困難。有些人崇拜史達林，但也有幾百萬人痛恨史達林的鎮壓。史達林死後還陰魂不散。改革者必須意志堅定，措施得力。慌亂必定會擾亂整個蘇聯的秩序。主席團的大多數成員認為，在不特意批評史達林的條件下實施改革。在蘇共中央委員會的會議上，他們只是提到晚年史達林的反覆無常。貝利亞因捏造英國情報機構代理人的罪名而被逮捕，貝利亞被逮捕後，蘇共中央主席團1953年7月召開了會議。實際上領導層擔心貝利亞會掌握最高領導權，也擔心他會實施看起來相當激進的改革。他們認為，應該對過去所犯下的罪行和權力濫用負責的是貝利亞，而不是史達林，1953年12月，貝利亞被處決了。
史達林的家庭也遭受了重大的變故。他的女兒斯維特蘭娜很快就改了自己的姓。學生時代大家都知道她的名字叫斯維特蘭娜·斯大琳娜，史達林死後，她自己改名叫斯維特蘭娜·阿利盧耶娃。由於已經向她父親的繼任者低頭，所以她最終倖免於難。瓦西里·史達林並未做相應的改變，經常沉湎酒色，臭名遠揚。史達林實際上已經和他脫離關係了，他父親死後，他被調查，並因愛胡鬧和濫用公共資金而被捕。他的特權歲月結束了。
史達林的屍體被抬出紅場陵墓
貝利亞倒台後，蘇共掌控了內務部。對於各民族有文化自決權的限制仍然比較多。馬林科夫和赫魯雪夫繼續推動改革，也都在為掌握最高權力而鬥爭。集體農莊的糧食收購價格上漲了。為提高糧食產量，哈薩克斯坦的荒地得到了開發。蘇聯與南斯拉夫的關係有了一定的緩和，同美國的緊張關係也有所鬆動，朝鮮戰爭也結束了。由於要明確支持蘇共主席團的每一項活動，所以在中央委員會上對發言管理就不那麼嚴格了。雖說蘇聯仍然是一黨專政，但總體上說，恐怖氣氛淡了。馬林科夫和赫魯雪夫之間的競爭還在繼續。貝利亞過去一直擔心他激進的改革思想和他個人的魯莽。馬林科夫缺乏自信，赫魯雪夫因鎮壓貝利亞而名聲大振，他在兩年的時間裡成了蘇聯的最高領導人。
在赫魯雪夫的授意下，一個委員會開始調查史達林時期大清洗的數據。赫魯雪夫雖然在尋找對馬林科夫不利的材料，但這尚需時日。蘇共主席團的幾位成員反對實施進一步的改革。為了保證自己能順利接班，赫魯雪夫在1956年的蘇共二十大上提出了史達林的問題。有人說破壞蘇聯秩序是危險的，他反駁說：「如果我們不在中央全會上說真話，我們在將來的某個時候可能不得不說出真話。那時候我們不是在發表演講，而是在接受人民的調查!」在蘇共二十大閉幕時，赫魯雪夫指責史達林是一個怪人，他整死了幾千人，在政治領導和具體政策上破壞了列寧主義的傳統。指控書並沒有全面綜合地評價史達林。赫魯雪夫的報告集中在從1934年基諾夫遇害以來史達林的活動上。他並不直接批評二十世紀二十年代後期以來蘇聯建立起來的基本政治經濟結構，他也沒提及史達林在內戰和第一個五年計劃實行期間實施的恐怖。為了贏得當時黨政官員的支持，他必須給人一種這樣的印象，你們這些人的前任都是1937—1938年大清洗的受害者。
整個會場都沒人提反對意見。赫魯雪夫達到了他的目的：對於他國內的競爭對手來說，很難指責他領導權的合法性，除非這個人想回到史達林的大恐怖年代。然而還有一個問題，正是史達林在東歐建立起了共產主義政權。通過指責史達林，赫魯雪夫重新確立了一條沿著列寧主義和十月革命的路線前進的道路。這在東歐國家行不通，因為這些國家是史達林幫助他們建立了共產黨政權。赫魯雪夫的報告對於東歐來說就是一顆政治炸彈。波蘭發生了有組織的罷工抗議活動。1956年10月，匈牙利也發生了動亂。
1957年6月，反對改革的人開始發起攻擊，他們要求赫魯雪夫辭去蘇共第一書記職務。但蘇共中央委員會支持他，經過幾年的激烈鬥爭後，他在1961年10月的蘇共二十二大上對史達林發起了更猛烈的攻擊。老布爾什維克朵拉·拉祖繼娜走上講台發言。由於她自己忍受了多年的壓制，她說列寧託夢給她說紅場的陵墓里只能有他一個。全場掌聲雷動。一個寂靜的夜晚，這件事情開始實施，經過防腐液處理的史達林的屍體被抬出了陵墓，埋在克里姆林宮的牆底下。在他的墓地上只有一根柱子和一座半身像。歷史學家開始查找史達林與列寧經常爭吵、舉止粗魯的材料。史達林格勒重新命名為伏爾加格勒。對列寧的崇拜，也在不斷提升著對赫魯雪夫的崇拜。1959年出版了新的黨史教程。那些崇拜史達林的黨員要麼保持沉默，要麼被開除黨職。只有一小撮在國外的共產黨員對此持有異議。他們當中最主要的是中國共產黨。毛澤東在生活上對史達林不滿，但他認為赫魯雪夫的改革是與史達林和毛澤東的共產主義決裂。這導致雙方關係出現裂痕，最後中蘇走向分裂。
赫魯雪夫1964年下台。蘇共政治局(主席團重新變成了政治局)推翻了赫魯雪夫在國內外實施的諸多政策，政治局也掩蓋了不同意見的爭論。但這是對赫魯雪夫政策的修正，不是要回到真正的史達林主義。新的蘇共中央總書記勃列日涅夫從沒考慮過實施恐怖統治或個人專制。「穩定幹部」成了一句口號。但實際上蘇共政治局在1969年史達林生日這一天打算重新評估史達林的遺產。《真理報》的社論準備了一份讚美詞，只是在最後一分鐘由於義大利和法國共產黨的干預才沒能公開發表。(但這也遲了，蒙古共產黨已經印發出去了，因為烏蘭巴托的時區要早一些。)
但重評史達林的動機還在。1984年7月，戈巴契夫上台前，政治局考慮過這個問題。年長的政治局成員對史達林還是有感情的，對赫魯雪夫很不滿。
為史達林恢復名譽的想法不了了之，因為戈巴契夫在1985年擔任黨的總書記後，他在政治局不再提這件事了。很快史達林又成為批判的對象。在戈巴契夫的公開性原則下，史達林濫用權力的許多材料被揭發出來了。史達林建立的行政命令製備受指責。電影、小說、詩歌以及歷史著作都在指責史達林。戈巴契夫通過知識分子的著書立說讓公眾明白，全面評估史達林的遺產對蘇聯社會的新生是十分重要的。但這一過程有點失控，因為有些批評史達林的人認為列寧對權力濫用也負有責任。他們將行政命令制的起源追溯到蘇聯成立的時候。但在公開討論中，也有人讚揚史達林，有人還是肯定了史達林在二十世紀三十年代蘇聯工業化以及反法西斯戰爭勝利中作出的貢獻。
但事情還沒結束。戈巴契夫指責史達林是歷史上最大的罪犯。1991年蘇聯解體，俄羅斯聯邦成立後，鮑里斯·葉爾欽還在批判史達林，與戈巴契夫不同的是，他既批判史達林，也批判列寧。批判一直持續到2000年普京當選俄羅斯總統。普京的祖父曾做過列寧和史達林的廚師。普京總統不想聽二十世紀三四十年代權力濫用的故事，相反他希望能夠宣揚那些年代蘇聯所取得的成就。普京不贊同詆毀前蘇聯，他象徵性地恢復了蘇聯的國歌，當然是換了歌詞了。他經常提及他在克格勃(KGB)工作的經歷，克格勃的前身就是史達林時期的安全保衛部門。為史達林恢復名譽顯然不是普京的目的，他是要說明俄羅斯帝國、蘇聯、俄羅斯聯邦是一脈相承的。自二十世紀八十年代後期以來，史達林第一次不再成為批判的對象。普京認為史達林就是一個歷史人物，他的是非功過讓學者們去評說就可以了。這對於長眠於地下的史達林來說是一種侮辱。只要他死後還被人們批判，他在莫斯科的政治中就仍是一個活生生的人物。普京上台後，史達林成了被官方忽視的人物。
