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

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

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

Генеральный прокурор принял ряд мер, направленных на искоренение бумажной волокиты в органах прокуратуры, значительно сократив требуемую от прокуроров отчетность. Своим приказом от 29 марта 1954 года он обязал их впредь предоставлять лишь отчеты о работе, донесения о наиболее опасных преступлениях и чрезвычайных происшествиях, а также копии представлений и протестов, вносимых в местные руководящие партийные и советские органы. Больше ничего от своих подчиненных прокуроры требовать не имели права. Он запретил прокурорам самолично устанавливать какую-либо отчетность, непредусмотренную приказом Генерального прокурора. Этим же приказом он отменил предоставление в вышестоящие прокуратуры различного рода справок о проведенных проверках, постановлений на арест, уведомлений о принятии к производству уголовных дел и т. п. Отменил также указание Прокуратуры СССР о личной проверке прокурорами республик, краев и областей раз в квартал одной тюрьмы или колонии. В то же время обязал прокуроров обеспечить строжайший надзор за соблюдением законности органами милиции и исправительно-трудовыми учреждениями, производя проверки там по своему усмотрению.

В апреле 1954 года в Москве состоялся V съезд профсоюза работников государственных учреждений, на котором серьезной критике подверглась работа органов прокуратуры по рассмотрению жалоб. На это Руденко моментально отреагировал, предупредив прокуроров о необходимости ликвидации проявлений бюрократизма и волокиты в разрешении жалоб, предложив заниматься этими вопросами и прокурорам республик, краев и областей.