Викторову удалось быстро сформировать группу, в которую вошли в основном бывшие фронтовики, окончившие после войны Военно-юридическую академию, в частности, Б. С. Нарбут, А. Г. Торопкин.

При создании специальной группы речь шла о реабилитации не только лиц, осужденных по политическим процессам, проводившимся до войны, но и жертв так называемого «военного времени», то есть лиц, которые вследствие тех или иных «обстоятельств» попали в плен, хранили случайно оказавшиеся у них фашистские листовки и т. п. Руденко предупредил, что могут быть «попытки поставить под сомнение правильность осуждения действительных врагов Советской власти, активных пособников фашистов, карателей, допустить реабилитацию таких лиц ни в коем случае нельзя».

В первые же дни работы специальной группы возникло множество вопросов, с которыми Викторов обратился к Руденко. В частности, есть ли политическое решение о массовом пересмотре дел прошлых лет и т. п. Вот что, по словам Викторова, Роман Андреевич ответил: «Поведение ваших товарищей объяснимо, им нелегко сразу воспринять все то, что вы им сообщили. Просят сослаться на решение о пересмотре дел прошлых лет? Что же, так привыкли. Не верят на слово? В академии так учили. Всем нам придется столкнуться с тем, что оценки некоторых событий и их участников, казавшиеся неизменными, нужно будет пересмотреть. Сделать это надо во имя истины, справедливости и правды истории. А решение будет. Оно готовится».

Руденко лично занимался вопросами реабилитации. Он подписал сотни постановлений следственных органов, признававших обвинения тех или иных лиц необоснованными и недоказанными, и вносил их на рассмотрение Верховного суда СССР. Он принял многих бывших узников, членов их семей, лично знакомил людей со следственными делами, разъяснял им права. Словом, помогал чем только мог.

Среди первых реабилитированных были и расстрелянные бывшие руководители Прокуратуры СССР и Прокуратуры РСФСР и их близкие: первый прокурор Союза И. А. Акулов и его жена Н. И. Шапиро, бывшие прокуроры республики Н. В. Крыленко, В. А. Антонов-Овсеенко и его жена Софья Ивановна, Ф. Е. Нюрина, Н. М. Янсон и его жена Л. Ф. Петрулевич и другие.

Конечно, без политического решения реабилитация жертв репрессий не смогла бы принять столь массовый характер. В январе 1956 года Президиумом ЦК КПСС была образована комиссия по изучению материалов о политических репрессиях в стране в период 1935—1940 годов. Ее возглавил секретарь ЦК КПСС, академик П. Н. Поспелов. В нее вошли также секретарь ЦК КПСС А. В. Аристов, Председатель ВЦСПС Н. М. Шверник, заместитель председателя Комитета партийного контроля при ЦК КПСС П. Т. Комаров. Активное участие в работе комиссии принимал и Генеральный прокурор Союза. Выводы комиссии легли в основу секретного доклада «О культе личности и его последствиях», произнесенного первым секретарем ЦК КПСС Н. С. Хрущевым 25 февраля 1956 года, в последний день работы ХХ съезда КПСС. В докладе впервые было сказано о беззакониях и произволе, творимых органами внутренних дел и государственной безопасности не только с попустительства, но и по прямому указанию И. В. Сталина.

Вот как описывает свои впечатления от этого доклада Викторов: «По инициативе Романа Андреевича Руденко я оказался с числе приглашенных на съезд. Это было глубоко впечатляющее, незабываемое событие в моей жизни... В конце работы съезда выступил Никита Сергеевич Хрущев. Его доклад о злоупотреблениях Сталина произвел большое впечатление. Еще свежа была в памяти всенародна скорбь. Прощаясь со Сталиным, многие искренне плакали. Все хорошо знали, помнили лозунг: «За Родину, за Сталина».