Смещение Берии, казалось, должно было облегчить процесс политической реабилитации. Но этого не произошло.
Остававшийся пока еще формальным лидером страны Маленков на июльском (1953 г.) пленуме ЦК КПСС ввел в оборот слова о «культе личности Сталина». Но для Маленкова этот культ означал, прежде всего, беззащитность партийно-государственной номенклатуры от произвола вождя. Будучи замешанным в организацию массовых репрессий, он, разумеется, не мог пойти на масштабный подход к этой проблеме.
Месяцы ушли на очередной передел власти внутри Президиума ЦК, расправу со сторонниками и родственниками Берии и других руководителей карательных служб, перестановку кадров в органах безопасности, внутренних дел и прокуратуры, пересмотр результатов объявленной по инициативе Берии амнистии. За активную роль в аресте Берии отблагодарили военных: состоялась реабилитация пятидесяти четырех осужденных генералов и адмиралов Советской Армии, в том числе близких Жукову — Телегина, Крюкова и Варенникова. Но многочисленные письма, поступавшие от заключенных, ссыльных и спецпоселенцев, оставались без ответа. Принятые в этот период решения отличало разве что более определенное указание на якобы главных виновников репрессий — бывших руководящих работников МГБ и МВД, которых судили в спешном порядке.
Лишь в начале 1954 г., когда в партийно-государственной верхушке четко обозначилось лидирующее положение Хрущева, реабилитация получила новый импульс. Хотя, взяв курс на расширение процесса реабилитации, на установление причин и последствий репрессий, Хрущев, как и свергнутый Берия, руководствовался далеко не бескорыстными мотивами. Об этом свидетельствуют, с одной стороны, сохранение в тайне статистических данных об арестованных органами ВЧК — ОГПУ — НКВД — МГБ за 1921–1953 гг. (они были подсчитаны, вероятно, по поручению первого секретаря ЦК, уже в декабре 1953 г.), а с другой, стремительная реабилитация участников «ленинградского дела». Хрущев хорошо усвоил сталинские методы использования компрометирующих материалов для ослабления соперников в борьбе за власть. Восстановление справедливости по отношению к ленинградцам компрометировало Маленкова, одного из виновников гибели Вознесенского, Кузнецова и их товарищей. Проведенная с широкой оглаской среди партийного аппарата, эта реабилитация укрепляла авторитет Хрущева, выстилая ему дорогу к единоличной власти.
Но какими бы мотивами ни руководствовались правители, чаяния и надежды политзаключенных и ссыльных стали постепенно сбываться. Наряду с установлением судебного порядка пересмотра дел (по Указу Президиума Верховного Совета СССР от 1 сентября 1953 г. Верховный Суд СССР получил право пересматривать по протесту Генпрокурора СССР решения коллегии ОГПУ, Особого совещания и двоек и троек) был введен и упрощенный порядок. В мае 1954 г. начала работу Центральная комиссия по пересмотру дел осужденных за «контрреволюционные преступления», содержащихся в лагерях, колониях, тюрьмах и находящихся в ссылке на поселении, созданы аналогичные комиссии на местах. Центральная комиссия получила право пересматривать дела на лиц, осужденных Особым совещанием при НКВД — МГБ или Коллегией ОГПУ; местные комиссии наделили функциями пересмотра дел осужденных двойками и тройками НКВД. Для изучения положения спецпоселенцев была образована комиссия под председательством Ворошилова, результатом деятельности которой стало известное постановление «О снятии некоторых ограничений в правовом положении спецпоселенцев» от 5 июля 1954 г. Были освобождены из ссылки ранее осужденные на срок до 5 лет за «антисоветскую деятельность», сняты ограничения по спецпоселению с раскулаченных и граждан немецкой национальности, проживавших в районах, откуда выселение не производилось.
В следующем году были выработаны предложения по пересмотру политики в отношении отдельных репрессированных народов. Первыми от спецпоселения были освобождены немцы. В этом определенную роль сыграло установление дипломатических отношений между СССР и ФРГ и состоявшийся в сентябре 1955 г. визит в Москву западногерманского канцлера Аденауэра. Тогда же был принят ряд актов об освобождении от спецпоселения и возвращении к местам прежнего проживания греков.