Побудований в 1958-1960 рр. (архітектори М. І. Гречина і А. І. Заваров, інженери В. І. Реп'ях і С. Чуднівська). Відкритий 9 грудня1960 року.

Конструктивною основою 4-поверхової споруди (довжина - 138 м, ширина - 78 м, висота - 18,5 м, загальний об'єм - 209 тис. м куб.) служить залізобетонний каркас. Фасади палацу - прозорі стіни зі скла, розділені струнким рядом колон каркасу та горизонтальними смугами панелей з алюмінію. Трибуни прямокутного залу для глядачів (66х102 м) в початковому варіанті вміщували від 8236 до 11 712 осіб. Спортивна арена (30х61 м) - на залізобетонній плиті; її можна використовувати для проведення змагань з 50 видів спорту, у тому числі зимових. Передбачено перетворення спортивної арени в партер, а сцени - в трибуну.

У 1980-1982 рр. здійснено реконструкцію Палацу спорту (інститутом Київпроект та Київським зональним науково-дослідним інститутом експериментального проектування). Освітлення та технічне господарство піддалися практично повної модернізації - розширили й інакше висвітлили інтер'єри та холи, палац оснастили численними роздягальнями та буфетами.

У 2004-2005 рр. в рамках підготовки до проведення музичного конкурсу «Євробачення» палац також зазнав реконструкції, у результаті якої значно але підвищено комфортність, але зменшено кількість посадочних місць до 8 000. При проведенні спортивних заходів максимальне число глядачів - складає 6 500 осіб.

16 квітня 2011 відбулася урочиста церемонія відкриття Палацу спорту, який перебував на реконструкції з жовтня 2010 року. Реконструкцію арени провели в рамках підготовки до проведення Чемпіонату світу з хокею в Першому дивізіоні. В рамках реконструкції повністю переобладнано закулісний простір, обладнані шість спортивних роздягалень, модернізовано освітлення залу, повністю замінено системи вентиляції, кондиціонування, обігріву, протипожежної безпеки. Крім того, над ареною з'явилося сучасне чотиристороння табло. На трибунах встановлені пластикові сидіння в кольорах національного прапора: загальна кількість місць складає 6800 глядачів (спортивний варіант). Концертний варіант з партером налічуватиме 9800 глядацьких місць.