По словам исследователей Софии, на этом месте был средневековый храм. О нём рассказывает лютеранский проповедник Стефан Герлах в 1578 году. Храм был однонефный, одноабсидный, построенный из дерева на каменном основании и покрытый двускатной крышей. С XV века в церкви хранятся мощи св. Стефана (канонизированый святой сербский король), из-за чего она была переименована в его память Св. Короля или Св. Стефани. С XVII века церковь Святой Недели позиционирует себя как просвещенный центр болгарской общины в городе. При ней была открыта церковная школа, а в 1839 году - общая школа. В 1849-1851 годах в южном дворе храма было построено школьное здание, а библиотека, созданная на пожертвования Ивана Дкнаелгу, осуществляла контроль (сгорела в 1880 г.).
В 1853 году старая церковь была разрушена и в тот же год болгарское население в Софии собирает значительную сумму на возведение новой. Брациговский мастер-строитель Иван Боянин, который строит величественное здание в 1863 г., придерживался возрожденческих традиций церковного строительства. Три купола и две фланкирующие вход башни колокольни возвышаются над окружающими постройками. В этих башнях храма были размещены 11 колоколов; восемь из них получили в качестве подарков в 1879 г. от российского имперского комиссара Болгарии князя Александра Дондукова-Корсакова, два были отлиты в Сербии. Храм Святой Недели мог похвастаться своим церковным хором, созданным сразу после Освобождения в 1878 году, по настоянию князя Дондукова. В соответствии с первым регулирующим планом Софии 1880 г. (Батенбергов план), вокруг церкви складывается площадь, а храм был модернизирован, расширен и обновлён арх. Николой Лазаровым (1898 г.). Церковь Святой Недели превращается в самый представительный столичный храм, а площадь около него называется Соборной - в самую главную в городе.
16 апреля 1925 г. в храме членами военной организации коммунистической партии был совершён теракт против царя Бориса III и высших военных и государственных служащих. В результате мощного взрыва во время опевания генерала Константина Георгиева (застреленного коммунистическим террористом) крыша церкви была разрушена, и под завалами погибло более 150 человек, а сотни были ранены.
Нынешний вид храм приобрёл в 1931 г. На сегодняшний день храм реконструрованный архитекторами Иваном Васильевым и Димитрием Цоловым представляет собой центральное купольное здание с колокольней на западе и включает в себя элементы старой ренессансной церкви. Сохранились праздничные иконы из старого храма, работы Николая Доспевски (XIX века), представителя Самоковская художественная школа. Фрески были реставрированы в 1971-1973 годах Николаем Ростовцевым с командой художников. Художник Иван Травницкий изготовил деревянный резной архиерейский престол.
Перед южным престолом, посвященным св. Стефану, установлена рака с мощами св. Стефан Милутина. В южной аркадной галерее находится могила Экзарха Иосифа - экзарх болгарского в 1877 г., а в северной - могила высшего священнослужителя Парфения, софийского митрополита с 1892 г.