Църквата “Света Неделя” е катедрала на Софийската митрополия. Тя заема мястото на стария площад Коручешме, който се славел със свой извор, засенчван от вековни дървета. Днес площадът се нарича “Света Неделя”.

През XIX и първите десетилетия на XX век храмът се нарича и “Свети Крал”, тъй като в него се съхранявали мощите на сръбския крал Стефан Урош II (1282-1321). Около 1460 г. по време на чумна епидемия Софийският митрополит Силваний ги пренесъл от селището Трепче, северно от Прищина, в днешния Люлински манастир “Св. Кирил и Методий” (наричан и “Св. Крал”). Впоследствие те били пренесени последователно в ротондата “Св. Георги”, в храма “Св. Безплътни сили” (или “Св. Архангели”), в митрополитската църква “Св. Марина”. Вероятно в началото на XVIII в. храм “Св. Неделя” станал митрополитски и мощите на сръбския крал били пренесени в него.

Вероятно първоначалната църква е била построена през X в. и както други тогавашни софийски храмове е била с каменни основи, а нагоре с дървена конструкция. В този си вид храмът просъществувал чак до средата на XIX в.

В началото на 50-те години на XIX в. Софийската митрополия и Софийската градска църковна община решили да изградят нов катедрален храм. На 7 май 1856 г. започва строежа на новата църква. Тя е трикорабна базилика с дължина 35,5 метра и ширина 19 метра.

През есента на 1863 г. строежът на новата църква е завършен (архитект Иван Боянин). Украсяването ѝ се проточва още няколко години и това забавя освещаването й. От 1863 до 1865 г. резбарят Антон Станишев изработва иконостаса. Част от иконостасните икони изписва големият живописец Станислав Доспевски. Освещаването на храма се извършва през 1867 година на празника 11 май.

При временното руско управление (1877-1879) княз Александър Дондуков-Корсаков подарява на храма комплект от 8 камбани с различна големина. Малките камбанарийки се оказват непригодни за тях и през 1879 г. се изгражда нова камбанария в южната част на храмовия двор.