Сградата е построена през 1528 година от Синан като джамия по заповед на султан Сюлейман Великолепни върху имот на Рилския манастир с метох. При разкопки през 1901 година са открити останки от стар християнски храм от V-VI век и още по-старо светилище на Асклепий.
Джамията е кръстена Коджа дервиш Мехмед паша на името на великия везир Соколлу Мехмед паша. Смята се, че архитект на джамията е прочутият Синан (архитектът на Сюлейман джамия в Константинопол). Храмът става известен с името Черната джамия, заради тъмния гранит, от който е направено минарето му. При земетресение през XIX век минарето на джамията пада и тя е изоставена.

След Освобождението на България през 1878 година сградата е превърната във военен склад, а по-късно в затвор.

Между 1901 и 1903 година сградата е преустроена в църква, която е осветена на 27 юли 1903, определен от Българската православна църква като Ден на успението на Свети Климент Охридски и Ден на Светите Седмочисленици — Светите светии Кирил и Методий и техните ученици и последователи Климент, Наум, Горазд, Сава и Ангеларий. Този ден се чества и като храмов празник. При преустройството са съборени минарето от черен гранит и медресето, намиращо се на мястото на днешната градинка пред църквата и са достроени ъгловите куполи, камбанарията и нартекса. Проектът за преустройството е на архитектите Йордан Миланов и Петко Момчилов.

Иконостасът в църквата е дело на дебърски майстори от рода Филипови. В двора на църквата, редом до неговата жена е погребан Петко Каравелов - един от водачите на Либералната партия, а по-късно на Демократичната партия. Той е брат на писателя Любен Каравелов и баща на Лора Каравелова - съпруга на поета Яворов. Гробът им се намира зад църквата.