Конечно, наиболее осязаемо условия жизни изменились для всех тех, кто после XX съезда КПСС был освобожден из лагерей (до 195 6 г. число освобожденных оставалось очень незначительным); очень много времени отнимала сама процедура реабилитации, связанная с прохождением дел через Верховный суд СССР или его «военную коллегию». С целью ускорения процедуры после XX съезда в лагеря были направлены специальные комиссии по пересмотру дел, получившие право решать вопросы на месте и немедленно освобождать реабилитированных. Результатом их деятельности стало освобождение в 1956 г. — году «возвращения», прекрасно описанном В. Гроссманом в его романе «Все течет», — нескольких миллионов человек. Это массовое возвращение, одновременно напоминавшее о том, что миллионы людей никогда не вернутся, не могло не вызвать смятения в умах и стало тяжелейшей социальной и моральной травмой, рожденной трагической встречей, предсказанной А. Ахматовой: «Теперь арестанты вернутся, и две России глянут друг другу в глаза: та, что сажала, и та, которую посадили».
Февраль 1957 г. принес реабилитацию народностям, депортированным в 1944 — 1945 гг. В родные места было позволено вернуться чеченцам, ингушам, балкарцам, карачаевцам и калмыкам, однако ничего не было сделано для немцев Поволжья и крымских татар, так как территории, которые их вынудили покинуть, были заселены русскими и украинцами.
В 1956 — 1958 гг. были реабилитированы — также выборочно — некоторые партийные и военные руководители, ставшие жертвами чисток. Среди них особенно много было военных (Тухачевский, Якир, Блюхер и др.), поскольку с 1953 г. армия была среди основных сил, поддерживавших Хрущева, а также руководящих партработников, чаще всего второстепенных и придерживавшихся сталинской линии (Эйхе, Рудзутак, Постышев, Косиор, Чубарь и др.), упомянутых в «секретном докладе». Эти частичные реабилитации, не коснувшиеся крупных исторических фигур большевизма, отстаивавших политические альтернативы сталинизму (Бухарин, Троцкий) или открыто выступавших против Сталина (Зиновьев, Каменев, Рыков и др.), не послужили импульсом для серьезных размышлений о природе сталинизме, массовых репрессий и ответственности за них партии в целом.
В то время как система лагерей (переименованных в «исправительно–трудовые колонии») подверглась реорганизации, а в КГБ произошла смена руководства (генерал Серов уступил свой пост бывшему первому секретарю ЦК ВЛКСМ Шелепину, сорокалетнему аппаратчику, не замешанному в чистках и твердо руководствовавшемуся партийными установками), советские юристы во имя «укрепления социалистической законности» отказались от традиций, укоренившихся при Вышинском. 25 декабря 1958 г. Верховный Совет принял новые «Основы уголовного законодательства», которые должны были стать базой для соответствующих Кодексов союзных республик. Отменялись наиболее вопиющие нормы в уголовном законодательстве сталинской эпохи; было упразднено понятие «враг народа»; с 14 до 16 лет был повышен возраст наступления уголовной ответственности; было запрещено прибегать к угрозам и насилию для получения признания; обвиняемый должен был обязательно присутствовать на процессе, защищаемый полностью ознакомленным с его делом адвокатом; за некоторыми исключениями, судебные заседания стали открытыми.