Через два с лишним месяца после смерти Сталина, 26 мая 1953 г. вспыхнуло восстание в норильском Горлаге. Более тысячи прибывших сюда ранее из Караганды заключенных – украинцев и балтийцев – создали подпольную организацию, и, когда охрана убила одного из них, часть заключенных объявила забастовку. Вскоре охрана снова открыла стрельбу, ранив нескольких человек. Заключенные сломали забор штрафного барака, освободили сидевших там 24 человека и взяли в заложники одного из начальников. На работу отказались выходить все 16 тысяч заключенных. После неудачной попытки переговоров лагерь был оцеплен войсками, получившими приказ его очистить. Несколько сотен сопротивлявшихся было убито.
Про восстание в Восточной Германии из западных радиопередач узнали заключенные Речлага в воркутинском угольном бассейне и решили следовать примеру немецких рабочих. Опыт забастовок у них уже был в 1951 и 1952 гг. 30 июня заключенные шахты Капитальная распространяли листовки «Прекратить подачу угля», а на стене шахты появилась надпись: «Угля не будет, пока не будет амнистии». За Капитальной последовала шахта № 7 и другие. К 29 июля 1953 г. бастовало 15 тысяч заключенных. Управление лагерями взяли на себя организованные заключенными стачкомы. Подавление забастовки шло по примеру Норильска.
Летом 1953 г. последовали забастовки в Караганде и на Колыме. В апреле 1954 г. в Кенгире (Казахстан) вспыхнуло самое большое восстание, длившееся 42 дня. В нем участвовало 9 тысяч мужчин и 4 тысячи женщин. Они проломили стену между мужским и женским лагерем, разрушили штрафной изолятор, освободив оттуда 252 человека, захватили кухню, склады и мастерские, где изготовляли холодное оружие. Прибывшая из Москвы комиссия вела переговоры о пересмотре приговоров, смягчении режима, ограничении рабочего дня, снятии номеров с одежды, расследовании незаконных расстрелов. Когда выяснилось, что переговоры ведутся для отвода глаз, пока будут стянуты войска, забастовка стала всеобщей. Избранный ее возглавлять заключенный подполковник Капитон Иванович Кузнецов выдвинул лозунг «Да здравствует советская конституция». В неравном 4-часовом бою 26 июня 1954 г. восстание подавили 1,7 тыс. солдат с пятью танками. Затем каратели отправились в Джезказган, где 20 тысяч заключенных неделей ранее объявили забастовку солидарности. Но они не подготовились к сопротивлению и сдались. В том же 1954 г. произошли волнения заключенных в лагерях Ревда (Свердловская область), Карабаш, Тайшет, Решоты, Джезказган, Балхаш и на Сахалине. В 1955 г. была повторная забастовка на Воркуте.
Под напором восстаний ЦК КПСС 10 июля 1954 г. постановил существенно облегчить лагерный режим: ограничить рабочий день, разрешить переписку, дать возможность покупать товары в лагерных ларьках. Была создана система комиссий по пересмотру политических приговоров. Заключенных, чей срок близился к концу, стали отпускать и без пересмотра. В 1955 г. была объявлена амнистия лицам, осужденным за сотрудничество с немцами во время оккупации. В связи с дипломатическим признанием ФРГ и визитом канцлера Аденауэра в СССР освобождены были и все немецкие граждане, остававшиеся еще в советском плену или в заключении.
«Реабилитация» осужденных по политическим статьям и роспуск лагерей очень ускорились после XX съезда КПСС в феврале 1956 г. До конца года было «реабилитировано» 617 тыс. заключенных. ГУЛАГ как ведомство был упразднен, его предприятия – такие как Норильск, Воркута, Дальстрой – были переданы гражданским министерствам, оставшиеся заключенные, преимущественно уголовники, размещены по тюрьмам и колониям, перешедшим в ведение Министерства юстиции.
Возвращение политзаключенных стало большим событием в жизни страны и встречи их, как с родными, так и с теми, кто донёс на них, были порой драматическими.
В феврале 1957 г. было разрешено вернуться из ссылки депортированным в 1944–1945 гг. чеченцам, ингушам, балкарцам, карачаевцам и калмыкам. Многие, запретам вопреки, стали возвращаться самовольно еще в 1956 г., после того, как Хрущёв осудил депортации с трибуны XX съезда. Правительство лишь узаконило реальное положение дел. На немцев Поволжья, месхетинских турок и крымских татар это решение не распространялось, хотя режим спецпоселенцев был отменен и для них. Первые стали впоследствии выезжать в Германию, вторые вернулись в Крым при Горбачеве. Возвращение репрессированных на родину сопровождалось межэтническими столкновениями, как в 1958 г. в Грозном.
25 декабря 1958 г. Верховный Совет принял новые Основы уголовного законодательства, которые окончательно отменяли сталинские процессуальные нормы и понятия вроде «враг народа», требовали обязательного присутствия обвиняемого на процессе и его защиты знающим его дело адвокатом.