Роман Андреевич Руденко родился 17 июля 1907 года в селе Носовка Черниговской губернии в многодетной семье крестьянина-бедняка. В автобиографии он писал: «До революции мой отец имел одну четверть десятины земли, работал по найму — плотничал, мать батрачила. После Октябрьской революции отец получил земли от Советской власти». Учиться сметливому юноше, которого за склонность к верховодству товарищи прозвали Ватажком, пришлось недолго. Надо было помогать большой семье, и он пошел работать на завод. Вскоре стал комсомольцем. С 1925 года на протяжении четырех лет он находился на комсомольской и советской работе, служил в рабоче-крестьянской инспекции. Часто публиковал заметки в местной печати, доводилось ему выступать и в суде в качестве общественного обвинителя.
В 1929 году Романа Руденко, только что окончившего юридическую школу, окружной комитет партии (ее членом он стал в 19 лет) направил в органы прокуратуры. Он стал работать следователем, а затем старшим следователем в окружной прокуратуре в Черниговской области. Затем постепенно поднимался по служебной лестнице: был помощником прокурора и прокурором города, заместителем прокурора области и, наконец, возглавил прокуратуру одной из крупнейших областей — Сталинской. Р. А. Руденко пользовался довольно высоким авторитетом в партийной среде и был на хорошем счету в Прокуратуре СССР. Когда в июне 1939 года встал вопрос о назначении нового Прокурора Союза ССР, выбор А. Я. Вышинского, уходившего на должность заместителя Председателя Совнаркома СССР, вначале пал на Руденко, но бывший в то время на Украине первым секретарем ЦК компартии Н. С. Хрущев не захотел отпускать от себя толкового прокурора, и назначение не состоялось. Прокурором Союза ССР утвердили М. И. Панкратьева.
В начале сентября 1940 года Роман Андреевич стал слушателем Высших академических курсов при Всесоюзной правовой академии, директором которых был тогда Шнейдер.
В марте 1942 года Р. А. Руденко назначили заместителем прокурора Украинской ССР, а в августе по приказу Прокурора Союза ССР В. М. Бочкова он возглавил специальную оперативную группу республиканской прокуратуры, став одновременно исполняющим обязанности Прокурора Украинской ССР. Эта группа после освобождения первых районов и городов Украины от немцев стала немедленно организовывать работу органов прокуратуры, направленную на полное восстановление правопорядка и законности. Вскоре прокуратура республики создала и другие оперативные группы прокуроров и следователей, которые входили в освобожденные местности Украины вместе с частями Красной Армии. В Киеве, например, оперативная группа стала работать уже в первый день его освобождения.
В одной из характеристик Романа Андреевича этого периода сказано: «Будучи и. о. Прокурора УССР, товарищ Руденко в сложных условиях работы в освобожденных от оккупации районах сумел правильно организовать прокурорскую и следственную работу периферии. Органы Прокуратуры УССР в специфических условиях прифронтовой обстановки активно способствовали правительственным органам и военному командованию в использовании сил и средств для разгрома врага, восстановлении народного хозяйства, ликвидации последствий оккупации».