Сградата е построена през [[1528]] година от [[Синан]] като джамия по заповед на султан [[Сюлейман Великолепни]] върху имот на [[Рилски манастир|Рилския манастир]] с [[метох]]. При разкопки през [[1901]] година са открити останки от стар християнски храм от V-VI век и още по-старо светилище на [[Асклепий]].
Джамията е кръстена '''Коджа дервиш Мехмед паша''' на името на великия везир [[Соколлу Мехмед паша]]. Смята се, че архитект на джамията е прочутият [[Синан]] (архитектът на [[Сюлейман джамия]] в [[Константинопол]]), но сигурни доказателства за това няма. Храмът става известен с името '''Черната джамия''', заради тъмния гранит, от който е направено [[минаре|минарето]] му. При земетресение през XIX век минарето на джамията пада и тя е изоставена. След Освобождението на България през [[1878]] година сградата е превърната във военен склад, а по-късно в затвор.
Между [[1901]] и [[1903]] година сградата е преустроена в църква, която е осветена на [[27 юли]] [[1903]], определен от Българската Православнаправославна Църквацърква като Ден на успението на Свети Климент Охридски и Ден на Светите Седмочисленици - Светите светии Кирил и Методий и техните ученици и последователи Климент, Наум, Горазд, Сава и Ангеларий. Този ден се чества и като храмов празник. При преустройството са съборени минарето от черен гранит и [[медресе|медресето]]то, намиращо се на мястото на днешната градинка пред църквата и са достроени ъгловите куполи, камбанарията и [[нартекс|нартекса]]. Проектът за преустройството е на архитектите [[Йордан Миланов]] и [[Петко Момчилов]]. Иконостасът в църквата е дело на дебърски майстори от рода [[Филипови]].
