На схилах біля храму не планували будувати житлові багатоповерхівки. Проте згодом архітектори та забудовники придивилися до ділянки та почали зводити будівлі.
У 1844 році за ініціативою священика костелу Святого Олександра, вулиця була вимощена каменем. Зважаючи, що історики записують “ксьондза”, можна припускати, щ йдеться саме про отця-поляка.
Забудовувати вулицю почали у 1910-х, коли мостова комісія склала проект зі зменшення ухилу цієї ділянки. Витрати на це покрили домовласники та парафіяни костелу Святого Олександра.
У радянські часи вулиця мала назву Челюскінців, однак після проголошення української Незалежності у 1991 році вулиця відновила історичну свою назву — Костельна.
Українські філологи кажуть, що правильно казати “вулиця Костельна”, а не “Костьольна”. Однак більшість парафіян, які бігають туди-сюди до храму цією дорогою, кажуть звично “Костьольна”, на польський манер. Між іншим, у неділю в соборі Святого Олександра польською мовою месу відправляють 1 раз на день, також діє польських хор та запрошують на заняття з польської мови дорослих та дітей. А ще є дві недільні меси українською, відправа на латині та англійською мовою. З кафедри не рідкість почути проповідь священика, який говорить українською з гарним польським акцентом.
Серед найстаріших будинків Костельної є прибуткові будинки №3 та №5, збудовані ще у 1871 році. До 1913 року вони належали різним власникам, поки їх не викупив відомий київський домовласник та підприємець Яків Каплер.
Перлиною неоренесансу вважається будинок № 4, зведений у 1888 році за проєктом Олександра-Петра-Адріана Шілє. До початку XX століття ця кам’яниця вважалася однією з найвищих у районі Хрещатицької площі.
Будинок №9, збудований у 1912-1913 роках техніком Абрамом Трахтенбергом. Замовником проєкту виступило Четверте товариство квартировласників, серед яких можна знайти імена відомих тогочасних юристів та адвокатів.