Палац одруження й реєстрації новонароджених побудований архітекторами В. І. Гопкало, В. М. Гречиною, інженером Н. М. Юрченко й відкритий в 1980 році до відкриття Олімпіади.

Палац став завершальним акордом ансамблю забудови Брест-Литовського (нині проспект Перемоги) та Повітрофлотського проспектів. Будівля знаходиться в невеликому парку з декоративним басейном і скульптурою «Либідь» і головним фасадом зорієнтована на проспект Перемоги. Ширина сходів головного входу надала урочистості всьому вигляду будівлі, встановленої на гранітному стилобаті. Завдяки своїй архітектурі, а також іронічному ставленню до шлюбу деяких киян, будівля отримала назву «бермудський трикутник».