Театр на Подолі народився ще тоді, коли номінально не існував, а на сірому київському культурному небосхилі з'явилося яскраве сузір'я, духовне співтовариство людей, які емоційно протистояли насаджуваній фальші, маючи намір звільнити творчу енергію не пов'язану з ідеологічними догмами суспільства. Це сталося в 1978 після гучного дебюту в Київському театрі російської драми ім. Л. Українки "Казки про Моніку" С. Шальтяниса, поставлену тоді ще просто юним режисером Віталієм Малаховым, який тріумфально увірвався на театральний Олімп, однозначно декларуючи свої домагання в мистецтві.
У 1979 році, напередодні Олімпійських ігор, державне керівництво вирішує поліпшити культурний вигляд столиці. Було прийнято рішення про створення чотирьох нових театрів : Молодого театру, Театру поезії, Театру на Лівому березі (до того що був при Укрконцерте) і Театру естради, де В. Малахов у свої 24 роки став першим головним режисером (до речі наймолодшим головним режисером в тодішньому СРСР).
У творчий колектив, в якому були актори, танцюристи, джаз-банд, вокалісти, влилися люди, з багатьма з яких Малахов працює до сьогоднішнього дня. Серед них: В. Ковалів, Т. Плашенко, А. Сергійко, А. Крижановський, І. Крикунів, Д. Малахова, А. Пархоменко, В. Андриенко. Тут починали свій творчий шлях А. Левіт, Л. Тебенькова, В. Іваненко, А. Кочнев, В. Чигляєв, А. Дяченко, А. Цекало разом з колективом-ансамблем "Капелюх". Не закінчивши 9-го класу, до Малахову прийшов Н. Джигурда, який, за словами Малахова, грав гномів і всяких незвичайних персонажів. У театр прийшли: В. Білоножко, Н. Рожкова, М. Битний-Шляхта, Т. Печенкіна, Г. Ткач, В. Ямненко, А. Середа. Звукорежисером працював Д. Ганапольский.
У 1987 році в Києві створений театр на Подолі на чолі з Віталієм Малаховым.
Формально цей театр був вже давно сформованим колективом творчих однодумців з "своїм стартовим капіталом" - це "Шинкарка", "Ніч чудес" та ін. Прийшов і перший комерційний успіх - договір з Тюменською нафтовидобувною компанією. Концерти в цьому регіоні принесли хороші гроші, що дало можливість улаштувати сцену і мати гідне фінансове положення.
З цієї миті театр Малахова стає "виїзним" - починається безпрецедентний етап великої кількості зарубіжних гастролей. У театр "поплили" спонсори. Оскільки виїжджати за кордон у той час було дуже складно, а театр мав такі можливості спонсори укладали угоди з театром і гастролювали зі своїми сім'ями. З 1987 року до 1994-го театр був практично мандруючим.
Акторам театру на Подолі аплодували в Луцьку, Львові, Полтаві, Ужгороді, Нижньому Новгороді, Севастополі, Ризі, Надыме, Донецьку, Дніпропетровську, Одесі.
Враховуючи високий професійний рівень колективу, його внесок у розвиток драматичного мистецтва України у 1994 році Головне управління культури Києва присвоїло театру на Подолі статус державного.
У репертуарі театру на Подолі більше 50 спектаклів. Творчий колектив театру і його художній керівник-директор Віталій Малахов стали лауреатами в 15 номінаціях\"Київської пекторалі" - найпрестижнішій театральній премії.
У 1998 році за спектакль "В степах України" А. Корнейчука театр отримав "Київську пектораль" в чотирьох номінаціях: за кращу режисуру, за кращий акторський ансамбль, за сценографію і за акторські роботи.
У 2003-2004 театральному сезоні спектакль"Дядя Ваня" А. Чехова в постановці В. Малахова став лауреатом "Київської пекторалі" в п'яти номінаціях: за кращу режисуру, за кращий акторський дебют (Е. Свирская), за кращу чоловічу роль (С. Бойка).
У 2006 році за указом Міністра культури творчому колективу присвоєно статус академічного за видатні досягнення в розвитку українського драматичного мистецтва.
У 2008 році директор-художественный керівник Київського академічного драматичного театру на Подолі Віталій Малахов став лауреатом Національної премії України ім. Тараса Шевченка в області мистецтва.
До дня незалежності України 2008 року Президент нагородив В. Малахова званням "Народний артист України".
У 2009 року в Театрі на Подолі відбулося 11 прем'єрних постановок. Театр активно готується до відкриття нової театральної будівлі. Спектаклі "Мертві душі", "Люксембурзький сад" в постановці з. а. України Ігоря Славинского стали лауреатами "Київської пекторалі- 2009" за кращу режисуру, актриса театру Софья Письман -дипломант премії за роль Коробочки в спетакле "Мертві душі". Театральною премією ним. Амвросія Бучмы нагороджений творчий колектив спектаклів "Мертві душі" і "Люксембурзький сад".
Прем'єра 2010 року, спектакль "Шість чорних свічок" по п'єсі культового шотландського драматурга Деса Диллона, поставлена н. а. артистом України Віталієм Малаховым, пройшла з величезним успіхом.