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

Прокурорам республик, краев и областей поручалось обеспечить посредством отделов уголовно-судебного надзора проверку каждого дела, по которому судами был вынесен оправдательный приговор или определение о прекращении дела, направленного в суд. В случае обнаружения необоснованного предания граждан суду или ареста решать вопрос об ответственности виновных.

Несмотря на столь строгий приказ, нарушения законности при аресте граждан продолжались и было их не так уж мало. Прокуратура СССР вынуждена была констатировать, что «некоторые прокуроры по-прежнему безответственно и легкомысленно относятся к санкционированию арестов». Видимо, все еще сказывались привычки и «навыки» прошлых лет, когда людей сажали за самые незначительные проступки. В результате проверки законности содержания в тюрьмах арестованных, произведенной на местах по поручению Прокуратуры СССР прокурорами шести республик и областей в мае 1956 года, было освобождено из-под стражи 239 человек. В приказе Генерального прокурора по этому вопросу приводились и конкретные примеры, которые свидетельствовали о том, что с гражданами все еще обращались как в былые времена. Так, прокурор одного из районов Баку за единичный случай обвеса покупателя арестовал продавщицу магазина, у которой на иждивении находились 9 человек, из них 7 малолетних детей. А в Московской области районный прокурор арестовал трех подростков за кражу голубей. И такие случаи были неединичными.

После введения в действие Положения о прокурорском надзоре Президиум Верховного Совета своим указом утвердил в апреле 1957 года новую структуру центрального аппарата Прокуратуры СССР. Теперь в аппарате стало 3 управления (следственное, кадров и хозяйственно-финансовое), 9 отделов, приемная, канцелярия (на правах отдела). В состав Прокуратуры СССР входили также Главная военная прокуратура и Главная транспортная прокуратура. При Генеральном прокуроре состояли следователи по особо важным делам и методический совет, а при Прокуратуре СССР — Всесоюзный научно-исследовательский институт криминалистики и журнал «Социалистическая законность», издаваемый совместно с Министерством юстиции и Верховным судом СССР.

Своим приказом Руденко утвердил и новую структуру прокуратур республик, краев и областей. Были упразднены отделы по надзору за органами милиции (их функции передавались следственным управлениям и частично отделу общего надзора); отделы с одиозным названием «по спецделам» переименовывались в отделы по надзору за следствием в органах госбезопасности; отделы уголовно-судебного и гражданско-судебного надзора —в отделы по надзору за рассмотрением в судах уголовных дел и гражданских дел; отдел по надзору за местами заключения (это слово резало ухо) — в отдел по надзору за местами лишения свободы, а справочно-информационный — в отдел систематизации законодательства.

Новая структура органов прокуратуры и даже другое наименование отделов подчеркивало те изменения, которые наметились в правоохранительной системе, как бы показывая, что с прошлым раз и навсегда покончено.