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