Палац існує вже понад 40 років. Будували його впродовж 1965-1970 років, а урочисте відкриття у квітні 1970-го «прив’язали» до 100-річчя від дня народження вождя більшовиків Володимира Ульянова-Леніна. Тепер уже мало хто пам’ятає, що раніше на місці палацу вирував Володимирський ринок. І надскладно знайти тих, кому вдалося на власні очі бачити Володимирську церкву біля ринку, адже її знесли ще в 1930-х роках. Про існування тут давніш торговиці та храму ми дізнаємося насамперед зі старих зображень і документів.

Ще в першій половині ХІХ століття на віддаленій частині Нової Забудови («Нового Строения» – так називали колись місцину вздовж Великої Васильківської вулиці) було організовано ринкову площу. Вона дістала назву Новостроєнської, або Володимирської – з огляду на те, що в 1833-1835 роках на торговельному майдані звели парафіяльну Володимирську церкву. Її парафію перенесли на Велику Васильківську з Печерська, де розгорнулося спорудження нової фортеці. Новозбудований храм був однобанним, дерев’яним на цегляному фундаменті, з присадкуватим куполом та шатровою дзвіницею. Його не надто показний вигляд більш-менш пасував до скромної околичної забудови прилеглих кварталів.

Проте до початку наступного, ХХ, сторіччя Нова Забудова ставала дедалі більш упорядкованою, сюди проклали трамвайну колію. Давня Володимирська церква здавалася вже надто старезною. Тож громада парафії вирішила спорудити солідніший цегляний храм, проект якого розробив штатний архітектор Київської єпархії Євген Єрмаков. Нову церкву було задумано в дусі візантійського зодчества, оформлення її фасадів нагадувало однойменний знаменитий собор у Києві. Будівництво розпочалося 1909 року. Парафія була не дуже заможною, через це роботи велися повільно, у міру накопичення коштів. Новий храм уже майже закінчили зводити, коли настала революційна доба.

Радянський уряд проголосив відокремлення церкви від держави, а офіційна ідеологія базувалася на атеїстичних поглядах. Тож годі було чекати на завершення будівництва храму за нових умов. Але саме нова Володимирська церква стала унікальним винятком з цього загального правила. У 1920- х роках влада підтримувала так звану обновленську («живу») церкву – розкольницьку конфесію, що відмежувалася від традиційного православ’я і всіляко демонструвала свою лояльність до більшовиків. Практично збудовану вже споруду біля Володимирського ринку передали обновленцям, які 1927 року освятили її, назвавши Преображенським собором. Утім, альянс безбожниківбільшовиків із «живою» церквою тривав недовго. Після того як обновленці посприяли радянським органам у послабленні православ’я, потреба в них відпала. Тому вже у 1930- х роках нещодавно освячений собор було зачинено та зруйновано, так само, як і стару Володимирську церкву. Відомо, що цю ділянку збиралися використати під гаражі.

Згодом для ринкового місця було знайдено нове застосування. У 1960-х роках виник задум щодо спорудження тут палацу з величезною залою, адже Жовтневий палац культури, який відігравав тоді роль республіканської аудиторії №1, вважався незадовільним як за розмірами, так і за якістю обладнання. До речі, місце розташування новобудови визначили не одразу. Наскільки відомо, працівники міського управління торгівлі не хотіли переносити ринок і домоглися того, що як альтернативу було запропоновано інше місце – на тогочасній Радянській (нині Михайлівській) площі, де раніше стояв зруйнований Михайлівський Золотоверхий монастир. Це могло б назавжди унеможливити відновлення втраченої святині. Проте керівник проектувальників Палацу «Україна» Євгенія Маринченко рішуче заперечувала проти цієї пропозиції. На нараді за участю перших осіб республіки вона зуміла довести неможливість перенесення місця будівництва. Для Володимирського ринку відвели іншу ділянку – на розі вулиць Горького та Тельмана. У 1968 році тут було споруджено новий критий ринок майже на 500 торговельних точок.

На колишньому місці торжища розпочалося зведення палацу на основі залізобетонної каркасної конструкції. До слова, у тогочасних публікаціях про нього згадували як про «кіноконцертний зал», а то й просто про «широкоекранний кінотеатр». Подейкують, що це було пов’язано з негативною реакцією Москви на будівництво нової київської споруди, яка могла б затьмарити нещодавно зведений Палац з’їздів у Кремлі. Тож кияни, зрештою, поставили союзне керівництво перед фактом.

Проект передбачав використання найновішого для тих часів обладнання – електроосвітлювального, світлотехнічного, акустичного, радіотехнічного тощо, керування яким зосереджено у спеціальному апаратному комплексі. Сцена, на котрій одночасно можуть розміститися 1500 осіб, одержала здатність трансформуватися відповідно до заходу, що проводиться. Між різними поверхами фойє влаштовано ескалатори. Інтер’єрам Палацу «Україна» надали розмаїтості та справжньої святковості. Для їхнього оздоблення було використано кольоровий газганський та білий уральський мармур, омелянівський і токівський червоні граніти, закарпатські блакитні та сіро-зелені туфи, казахстанський камінь-черепашник, натуральну деревину – горіх, клен, ясен. Оригінальні світильники з литого скла мали відтінок льоду, що тане.

Надзвичайно своєрідним став зовнішній вигляд палацу, у якому поєднано конструктивні та декоративні особливості. Головним мотивом оформлення динамічного угнутого фасаду є ребра-струни, обличковані анодованим алюмінієм, що ніби перетворюють будівлю на величезний музичний інструмент. Виразної пластичності й асиметрії додають касова зала, прибудована праворуч, і сходи на навіс-терасу, розташовані ліворуч. В оздобленні екстер’єру використано білий мармур, світло-сірий та брунатно-червоний граніт, білий вапняк. Особливої людяності будівлі надавали величезні прозорі вікна, котрі відкривали назовні те, що відбувалось у фойє.

Авторами проекту Палацу « Україна» є архітектори Є.Маринченко, П.Жилицький, І.Вайнер, інженери П.Булаєвський і В.Сидорченко. За цю визначну роботу Євгенія Маринченко та Петро Жилицький 1971 року (посмертно) були нагороджені Державною премією УРСР імені Тараса Шевченка. Іноді споруду називають Палацом культури «Україна». Проте авторка проекту Євгенія Маринченко завжди наголошувала, що це неправильне тлумачення, бо «палац культури» є радше клубним закладом, а «Україна» – саме палац для визначних державних і мистецьких подій. Таке розуміння відбите й у назві розташованої поряд станції метро – «Палац «Україна»» (колишня «Червоноармійська»).

Упродовж 1996-1998 років було здійснено капітальну, вельми витратну реконструкцію палацу. Загальна об’ємно-просторова композиція будівлі залишилася такою, як і раніше, а зовнішній та внутрішній вигляд споруди зазнали певних змін. Усередині, зокрема, оновлено технічне устаткування, приміщення зроблено більш пишними й ефектними (насамперед, залу для урочистих банкетів).

Додано нові гобелени та велике керамічне рельєфне панно «Золотоверхий Київ» (скульптори В.Прядка, О.Олійник). Для вікон чільного фасаду було використано темне тоноване скло, через що, на жаль, палац набув не властивого йому раніше холодного, відчуженого вигляду. Назва давньої торговиці та колишньої Володимирської церкви досі відбивається в найменуванні розміщеної поблизу Володимиро-Либідської вулиці. Можна ще додати, що поряд із Володимирським ринком тепер знову постала сакральна будівля. Розроблено проект спорудження тут, біля вулиці Тельмана, нового Володимирського храму. У 2001-2002 роках згідно з цим задумом було зведено першу чергу, яка нині діє як окрема церква в ім’я Преподобної Єфросинії Полоцької. Цегляний однобанний храм оформлено у стилістиці бароко. А неподалік, в орендованому приміщенні на вулиці Володимиро-Либідській, 1, 2005 року було відкрито Свято-Володимирський духовно-просвітницький центр.