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