Умение держать нос по ветру всегда отличало советскую «творческую интеллигенцию»: и когда она рыдала после смерти диктатора, и когда рьяно критиковала Сталина, узнав о докладе Хрущева на XX съезде партии, и когда громила «антипартийную группу Маленкова, Молотова, Кагановича и примкнувшего к ним Шепилова» или восхваляла нового «вождя» Никиту Сергеевича Хрущева, а затем — сменившего его Леонида Ильича Брежнева.
Руководство стремилось осуществлять десталинизацию, оставляя неприкосновенным имя самого Сталина, даже ссылаясь на него. Так, газета «Правда» 10 июня 1953 года впервые обратилась к критике культа личности, но при этом использовала «основополагающие указания» уже усопшего «великого вождя и учителя». Преемник Хрущева на посту «первого большевика» Украины, член Президиума ЦК КПСС Мельников в своем докладе 21 января 1956 года все еще говорил о «великом учении Маркса — Энгельса — Ленина и Сталина». Первоначально критика культа личности носила пассивный характер. Просто имя Сталина стали реже упоминать, меньше цитировать его слова, кое-где сняли портреты.
27 марта 1953 года был опубликован указ Президиума Верховного Совета СССР «Об амнистии», на основании которого подлежало освобождению из заключения около одного миллиона осужденных. Действие указа не распространялось на приговоренных к лишению свободы на срок более пяти лет за «контрреволюционные преступления, крупные хищения социалистической собственности, бандитизм и умышленное убийство». Тогда же из лагерей и ссылки возвращаются близкие, друзья и соратники членов Президиума ЦК партии.
4 апреля в газетах появилось сообщение МВД о тщательной проверке всех материалов предварительного следствия по «делу врачей», которая показала, что обвинения являются ложными, показания арестованных получены путем применения недопустимых методов Следствия, Все, привлеченное по «делу, врачей» были полностью реабилитированы и освобождены из-под стражи. 6 апреля в передовой статье «Правды», озаглавленной «Советская социалистическая законность неприкосновенна», в связи с пересмотром «дела врачей» были выдвинуты обвинения в адрес бывшего министра госбезопасности С. Игнатьева и бывшего заместителя министра М. Рюмина. Игнатьев был освобожден от обязанностей секретаря ЦК партии, а Рюмин отдан под суд.
Постепенно в ЦК партии стало поступать все больше и больше просьб родственников бывших высокопоставленных функционеров и хозяйственных работников, осужденных при Сталине. Центральный Комитет и Центральная Контрольная Комиссия рассматривали эти заявления и, как правило, принимали положительные решения. Однако это пока что было восстановлением справедливости в отношении отдельных лиц, но не массовой реабилитацией.
По данным министра внутренних дел С. Круглова, перед смертью Сталина в тюрьмах и лагерях находилось около четырех миллионов человек, а «спецпереселенцев» насчитывалось более двух с половиной миллионов. В 1953–1954 годах всю систему ГУЛАГа потрясли крупные восстания. Летом 1953 года — Воркута и Норильск, в конце того же года — Унжлаг и Вятлаг. Летом 1954 года разразилось мощное восстание заключенных в поселке Кингир в Казахстане. Все эти выступления были жестоко подавлены, нередко с применением танков.
В сентябре 1953 года был издан указ Президиума Верховного Совета СССР, предоставивший Верховному суду право пересматривать по протестам Генерального, прокурора решения бывших коллегий ОГПУ, «троек» НКВД и «особого совещания» при НКВД — МГБ — МВД СССР. Тогда же были упразднены военные трибуналы войск МВД.
В 1954 году создаются центральные и местные комиссии по пересмотру лиц, осужденных по политическим обвинениям в 1934–1953 годах. Но широкий пересмотр дел политзаключенных начался только в середине 1955 года. При этом ведущую роль в процессах реабилитации играет Хрущев. В это время уже шла подготовка к XX съезду партии, и Центральный Комитет одним из основных вопросов при разработке материалов к съезду считал массовые политические репрессии.
К осени 1955 года был собран уже достаточно большой материал о политических репрессиях и об ответственности Сталина за это. Именно тогда Хрущев начинает вплотную заниматься этими вопросами. Однако, проводя реабилитацию сталинских узников, Хрущев и его соратники стремились ввести в заранее определенные рамки критику Сталина и сталинизма. В тех случаях, когда эти рамки не соблюдались, принимались самые жестокие меры. Особенно четко это проявилось после XX съезда КПСС, когда на партийных собраниях рядовые коммунисты резко критиковали деятельность партии, ее руководящих органов. Звучали предложения о снятии памятников Сталину, переименовании городов и улиц, наказании всех виновных в массовых репрессиях 30-40-х годов.
