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

Одновременно решались кадровые вопросы.

Руденко, как правило, своих заместителей, а также начальников управлений и отделов, считавшихся старшими помощниками Генерального прокурора, подбирал лично. Конечно, приходилось считаться и с ЦК партии, в первую очередь с отделом административных органов, откуда ему тоже «поставляли» кадры руководящих работников. При нем в центральном аппарате установилась довольно основательная стабильность в кадровом составе, чехарда, происходившая в предыдущие годы, прекратилась. Люди почувствовали себя уверенней и спокойней. Своих заместителей он менял нечасто, в основном при уходе их на пенсию либо переходе на другую руководящую работу. Достаточно отметить, что при нем почти четверть века первыми заместителями Генерального прокурора были только четверо: П. В. Баранов, А. Н. Мишутин, М. П. Маляров и А. М. Рекунков. Все они — люди неординарные, прошедшие хорошую прокурорскую выучку на разнообразных должностях, включая самые низшие, то есть начинали со следственной работы в районах или помощниками прокурора, а затем шаг за шагом поднимались по службе, получая по праву чины и награды. Некоторые прошли суровую армейскую школу во время Великой Отечественной войны на прокурорских или командирских должностях. Другими словами, никто из них не был случайным человеком в органах прокуратуры.

Первым, кому Руденко предложил пост своего основного заместителя, был прокурор РСФСР Павел Владимирович Баранов. По свидетельству С. В. Тюрина, именно к нему поехал Руденко сразу после своего назначения на должность Генерального прокурора СССР. «Этот жест уважения был по достоинству оценен», — пишет Тюрин. И действительно вскоре, 13 апреля 1954 года, Баранов переместился с Кузнецкого моста, где располагалась Прокуратура РСФСР, на Пушкинскую улицу, в дом 15 а, и занял кресло первого заместителя Генерального прокурора СССР.

Павел Владимирович Баранов родился 13 августа 1905 года в Петербурге. В 14 лет стал работать в мастерских Витебского губернского совнархоза, затем некоторое время учился в ФЗУ, где получил специальность электромонтера, был секретарем комсомольской организации в Ленинграде и Петрозаводске, а в 1931 году по направлению партийных органов занял должность прокурора Дновского района Ленинградской области. Через несколько лет стал прокурором Кировского района Ленинграда, а в 1937 году — Свердловской области. Незадолго до войны Баранов возглавил уголовно-судебный отдел прокуратуры Ленинградской области. Когда началась Отечественная война, Павел Владимирович был мобилизован в действующую армию и прошел путь от помощника военного прокурора Ленинградского фронта до военного прокурора 2-го Белорусского фронта, став полковником юстиции. После того как отгремели бои, он некоторое время занимал должность военного прокурора Северной группы войск, а затем — Южно-Уральского военного округа. В органах военной юстиции Баранов проработал в общей сложности 7 лет, был награжден двумя орденами Красного Знамени, орденом Отечественной войны 1 степени и другими. 19 апреля 1948 года был назначен на должность заместителя прокурора РСФСР, а с 21 августа того же года стал исполнять обязанности прокурора республики и вскоре был утвержден в этой должности, прослужив в ней чуть более пяти лет.

Первым заместителем Генерального прокурора СССР Баранов оставался три года. 3 мая 1957 года он был назначен первым заместителем председателя юридической комиссии при Совете Министров СССР, образованной по прихоти Хрущева вместо упраздненного Министерства юстиции. В 1961 году Павел Владимирович вышел в отставку. Скончался он в 1988 году.

Основной заботой Руденко была подготовка нового Положения о прокурорском надзоре, так как предыдущее (принятое I7 декабря 1933 года) давно уже устарело. Создалась парадоксальная ситуация, когда прокуроры, осуществляющее надзор за законностью в стране, сами не имели законодательного документа, определяющего их права и обязанности по осуществлению этого надзора.

19 января 1955 года в центральной печати было опубликовано постановление ЦК КПСС «О мерах по дальнейшему укреплению социалистической законности и усилению прокурорского надзора» — первое партийное решение за последние три десятилетия, ориентирующее все государственные и советские органы на необходимость укрепления законности в стране. Особая роль при этом отводилась органам прокуратуры, которые призваны были обеспечить надзор за строжайшим соблюдением законов, особенно при производстве следствия по делам, расследуемым органами внутренних дел и госбезопасности. В связи с этим было признано целесообразным принять специальное Положение о прокурорском надзоре в СССР.

Проект Положения был подготовлен при непосредственном участии Генерального прокурора СССР, а также его первого заместителя Баранова и представлен в ЦК КПСС. Постановлением от 19 января 1955 года проект получил одобрение, и в феврале 1955 года Прокуратура СССР представила его в Президиум Верховного Совета СССР, после чего он был направлен всем президиумам Верховных Советов союзных республик. Одновременно проект рассматривался в юридическом отделе Президиума Верховного Совета СССР, Верховном суде СССР, Минюсте СССР и других ведомствах. От всех заинтересованных организаций в Союзную прокуратуру поступило около 60 различных замечаний и предложений. Все они тщательно анализировались и в подавляющем большинстве были приняты.

Например, заместитель председателя Президиума Верховного Совета СССР М. П. Тарасов внес предложение дополнить Положение новой статьей, предоставляющей прокурору право приостанавливать исполнение опротестованных приговоров и решений, вошедших в законную силу.

Председатель Президиума Верховного Совета Белорусской ССР В. И. Козлов предложил повысить назначать лиц на должности прокуроров в городах и районах не с 23 лет, как было предусмотрено в проекте Положения, а с 25.

Член Президиума Верховного Совета СССР И. В. Капитонов считал, что так называемые «генеральские чины» работников прокуратуры — государственный советник юстиции 1, 2 и 3 класса — должны присваиваться по представлению Генерального прокурора Президиумом Верховного Совета СССР.

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

Статья 30 проекта Положения о прокурорском надзоре устанавливает право Генерального Прокурора опротестовать постановление Пленума Верховного суда СССР в Президиум Верховного Совета СССР.

Товарищ Волин (я главным образом буду говорить о нем, ибо он является главным оппонентом по этому вопросу) считает, что постановление Пленума Верховного суда СССР не может быть опротестовано в Президиум Верховного Совета СССР, что Пленум Верховного суда СССР — это высшая инстанция...