Родился 26 января 1959 года в Свердловске (ныне - Екатеринбург) в семье военного.

Окончил металлургический техникум по специальности "прокатное производство", затем учился в Свердловском архитектурном институте. Когда учился на третьем курсе, в Свердловск приехал Малый театр. И Руденский решил пойти к известному актеру и одновременно директору театра Виктору Коршунову посоветоваться насчет поступления в театральный. В московское Щепкинское училище поступил сразу на второй курс.

Училище Андрей окончил в 1984 году. Осенью того же года его пригласили на пробы к режиссеру Виктору Титову, который готовился снимать « Жизнь Клима Самгина ».

С 1993 года по 2001 год играл в труппе "Нового Драматического Театра".

В 1989-1993 годах играл в московском Новом драматическом театре, в основном - роли романтических героев (например, в спектакле "Орленок" по Э.Ростану). Самая яркая театральная роль: Виконт де Вальмон в "Опасных связях".

В кино актер дебютировал в главной роли в телесериале по роману М.Горького "Жизнь Клима Самгина" (1986-88). После этой работы, принесшей ему признание зрителей и специалистов, Руденскому с выбором ролей пришлось трудно, слишком высокую планку он сразу взял. Поэтому он всегда так тщательно читал сценарии и больше отказывался, чем соглашался. Потом был телефильм «МОРСКОЙ ВОЛК» по роману Джека Лондона - и опять главная роль.

Очень гордится Руденский своим участием в фильме «БРАТ НАШЕГО БОГА» мэтра польского кино Кшиштофа Занусси.

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

Андрей Руденский один из самых популярных и успешных актёров современного кинематографа.