Уже через месяц после смерти Сталина все центральные газеты поместили краткое, но замеченное везде и поразившее всех сообщение, что арест большой группы выдающихся врачей был произведен «бывшим МГБ» незаконно и неправильно и что для получения «нужных» признаний органы МГБ «применяли недопустимые и строжайше запрещенные законом СССР приемы следствия». В одной из передовых статей газеты «Правда» в эти дни говорилось о реабилитации «выдающегося советского артиста Михоэлса» и о попытках «провокаторов из бывшего МГБ» разжечь в стране национальную рознь. Уже к концу апреля из заключения вышло более тысячи человек, почти все они еще недавно занимали крупные посты в советской и партийной иерархии. Среди них была и большая группа генералов и адмиралов, арестованных и осужденных по разным обвинениям после войны и реабилитированных теперь по настоятельному требованию маршала Георгия Жукова, занявшего по предложению Хрущева пост первого заместителя министра обороны СССР и фактически взявшего под свой контроль Вооруженные Силы СССР. Арест Берии летом 1953 года, а также суд и расстрел как Берии, так и некоторых его ближайших сподвижников ускорили реабилитацию многих тысяч партийных и государственных деятелей, ставших жертвами послевоенных репрессий. В первую очередь были отменены приговоры по так называемому «ленинградскому делу»: в 1949–1950 годах в Ленинграде и в Москве по обвинениям в сепаратизме и национализме были арестованы тысячи партийных и советских работников, в том числе член Политбюро Н. А. Вознесенский и секретарь ЦК ВКП(б) А. А. Кузнецов, а также многие члены ВКП(б), работавшие и отличившиеся в годы войны в осажденном Ленинграде. Были прекращены кампания против «безродного космополитизма» и антиеврейская кампания, каждая из которых также требовала немалых жертв. О более мелких антитеррористических кампаниях я уже не говорю. По отдельным ходатайствам начали пересматриваться и многие дела и обвинения довоенного времени. Отдельные сохранившиеся в живых узники лагерей, оказавшиеся там еще в 1930-х годах, появились в Москве.

Печать почти ничего не сообщала об этих реабилитациях и о людях, возвратившихся к своим семьям. Однако друзьям и родным они рассказывали почти все. К тому же решения по каждому из таких дел принимались в 1953–1954 годах не единолично, а коллегиально. С марта 1953 года и до конца 1954 года прошло множество заседаний в ЦК КПСС, в Прокуратуре СССР, в коллегиях Верховного суда СССР, а также на разных уровнях в органах государственной безопасности. Рассматривались не только бумаги, но также показания свидетелей и самих заключенных, требовавших реабилитации. Дела двигались медленно, но к концу 1954 года было реабилитировано более 10 тысяч недавних заключенных, главным образом из числа ответственных работников. Немало таких людей было реабилитировано посмертно.

Общее давление на верхи партии возрастало; во всех партийных и государственных инстанциях находились уже сотни тысяч заявлений о реабилитации, и игнорировать эти документы было все труднее. Почти каждая реабилитация, а тем более каждое освобождение заключенного из лагеря приводили в движение всех заключенных. Волновалась и администрация лагерей, имевшая до сих пор неограниченную власть над узниками. В стране имелись еще тысячи лагерей, и судьбу находившихся там заключенных должны были решить Н. Хрущев и другие члены партийного руководства. Затягивание было опасно, отдельные забастовки и проявления недовольства прокатились по северным лагерям еще в 1954 году. В 1955 году в отдельных крупных лагерях прошли восстания; наиболее известным из них было описанное А. Солженицыным восстание в Кенгире. Оно было жестоко подавлено с использованием танков. Однако остановить расширение и углубление недовольства заключенных было уже невозможно. Ни в Советском Союзе, ни за границей об этих событиях ничего не знали.