Будапеща е превзета през 1526 и в същата година е поставено началото на строежа. Сградата е завършена две години по-късно, както гласи османски надпис, открит върху паметна плоча от бял мрамор, поставена над вътрешната входна врата на храма. Коджа дервиш Мехмед паша джамия е наричана още Черната джамия заради своето минаре, до половина изградено от черен мрамор или черен витошки гранит. Смята се, че архитект на сградата е самият Синан – най-големият османски майстор и авторът на храмовете Сюлеймание в Истанбул, Селимие в Одрин, както и десетки други, сред които и Молла Ефенди джамия, позната на софиянци като Баня башъ.
Към Черната джамия са построени допълнителни обществени сгради и помещения като имарет, хамам и кервансарай. Векове наред най-голяма площ от днешната градина заема мюсюлманското духовно училище, наричано „медресе“. Но с упадъка на Османската империя средствата за поддръжка на Коджа дервиш Мехмед паша джамия и комплекса около нея намаляват, храмът е изоставен и превърнат в хранилище за боеприпаси, а медресето и имаретът са превърнати в затвор.
След Освобождението храмът буди смущение у много столичани със страховития си облик. Той е запечатан в спомените на Райна Костенцева, която разказва:
„Джамията имаше зловещ външен вид. Високите ѝ каменни зидове бяха почти почернели. Те се издигаха застрашително над безлюдната улица и всеки, който минеше тук, бързаше по-скоро да се отдалечи, защото се мълвеше, че понякога в нея вкарвали хора, грабвани от улицата… При липса на улично осветление в София, особено в покрайнините, дето се намираше и Черната джамия, силуетът на постройката дори и при пълна луна навяваше ужас.“
Сред личностите, хвърлени в затвора пред джамията, е Петко Каравелов – един от авторите на Търновската конституция, политик, заемащ поста министър-председател четири пъти и брат на поета революционер Любен Каравелов. Държавникът влиза за пръв път в затвора за кратко в началото на 1887 без съд и присъда след русофилските бунтове. Общественикът Добри Ганчев твърди, че тогава политикът е пребиван и унижаван в килията си от майор Коста Паница:
„Когато подир бунта в Силистра и Русе в столицата арестуваха русофилите, П. Каравелов бе затворен в Черната джамия. Един ден Паница взема за другар известния на времето нехранимайко и пияница, съдържател на заведение… Робчето се казваше. Някогашен харамия. Отива с него в Черната джамия. По няколко камшика на всички затворени русофили. А на Каравелова нещо повече. Ритал го, удрял го, плюл го. А пък Робчето, по заповед на главатаря си, още по-жестоко оскърбил бившия министър-председател.“
Скоро след това съпругата на Петко Каравелов – Екатерина, започва да търси справедливост за мъжа си. Обръща се към редица дипломатически представители в София и споделя за издевателствата върху големия политик. Те са възмутени от случилото се и се срещат лично с него. В присъствието на чуждестранни журналисти държавникът е запитан за инцидента. Тогава Каравелов гордо отговаря:
„Господа, в моето отечество такива работи не стават!“
Английският писател и пътешественик Джеймс Самюелсън посещава София през 1888, когато Петко Каравелов вече е на свобода. Едно от малкото обществени места, които представляват интерес за писателя, е софийският затвор. Авторът споделя, че килиите са разположени в поредица от сгради, ползвани преди това от мюсюлманското духовно училище. Затворниците спят върху дървени рафтове, а облеклото им е изработено от бял брезент. Изключение прави един свещеник, осъден за подбудителство, на когото е позволено да носи своите расо и калимявка. По това време, според Самюелсън, задържаните са около 180 души – 170 мъже и 7 жени, разделени по пол. Почти всички излежават дългогодишни присъди за тежки престъпления като грабеж или убийство. Много затворници изработват бижута от цветни мъниста или плетат шалове и чорапи, които продават на посетителите, за да припечелват. Освен това задържаните не осъществяват допълнителни дейности. Според писателя това безделие води до постоянни опити за бягство, които нерядко са успешни.
На 15 март 1891 е осъществен неуспешен атентат срещу министър-председателя Стефан Стамболов. Около 20:00 той и финансовият министър Христо Белчев вървят по днешния Дякон Игнатий. Тогава, в тъмнината на неосветения град, става престрелка. По грешка е убит Христо Белчев, а Стамболов остава невредим. Заловен е само един от атентаторите – Денчо Тюфекчиев, но министър-председателят използва случая, за да се справи с политическите си противници. Арестуваните са стотици. Петко Каравелов не е участвал в атентата, но получава петгодишна присъда и през 1892 влиза за втори път в затвора пред Черната джамия. Сред осъдените е и поетът Светослав Миларов, който е обесен в двора на затвора. За кратко в къща на ъгъла на улиците Граф Игнатиев и Шести септември живее Кирил Христов, който разказва в спомените си:
„Но най-печалната подробност на тая гледка от моя балкон беше бесилката, която стърчеше на самия югозападен ъгъл зад зидовете на Черната джамия – точно на мястото, гдето е сега веселата будка за вестници и цигари. Не можех да изляза на балкона и да не изскочи пред очите ми недосъздаденият поет Светослав Миларов, който бе немного отдавна увиснал тук на въжето. И само той ли!“
Петко Каравелов не излежава цялата си присъда, защото получава амнистия в края на 1894 от правителство на Константин Стоилов. Свещеноиконом Димитър Калев споделя, че след освобождаването на Петко Каравелов, килията му е превърната в затворническа църква. Останалата част от затвора е описана подробно от Георги Каназирски-Верин:
„…Имарет джамиси, заедно с градинката пред нея, тогава беше централен затвор и я наричаха Черната джамия. Целият парцел беше заобиколен от високи каменни зидове. Главният вход беше откъм ул. 6 септември, срещу днешната прогимназия. Там беше и военният пост. Около стените се разхождаше постоянен военен патрул. В Черната джамия се влизаше най-напред в първия двор, част от днешната градинка. Там беше караулното помещение и военен вещеви склад. През втората врата се влизаше във втория двор, гдето имаше пристройка с килии за по-маловажни престъпници, една кафеджийница, един бръснар и една лавка.“
В края на XIX век Общинският съвет взема решение да бъде отпуснато мястото, на което днес се издига сградата на Шесто основно училище Граф Игнатиев, за построяването на нова църква в столицата. Петко Каравелов, обаче е застъпник на идеята мюсюлманският храм да бъде преустроен, вместо да се търси място за нова сграда. В своя статия държавникът пише:
„Хубавата сграда на джамията ще се запази от разрушаване и с малко пари ще се обърне във великолепен храм, какъвто няма по цяла България, когато проектираната нова църква, поради липса на достатъчно средства, не ще се построи скоро и ще бъде малка и няма да се отличава от другите наши църкви… Нам ни трябват високи, светли храмове, да подигат религиозното чувство – тесни, тъмни подземия имаме и тъй достатъчно.“
Каравелов взема позиция и относно името на храма, като обръща внимание на делото на Светите братя Кирил и Методий и техните петима ученици Климент, Наум, Горазд, Сава и Ангеларий:
„Ние предлагаме тази църква да се нарича Св. Седмочисленици или както ги зоват още светите Светлозарни учители, на които толкова много дължи славянството.“
Впоследствие правителството взема решение Коджа дервиш Мехмед паша джамия да бъде превърната в православен храм с името Св. Седмочисленици. След изборите през 1901 Петко Каравелов става министър-председател на Княжество България и работата по превръщането на джамията в църква започва, въпреки трудностите от вътрешно- и външнополитически характер.
Черната джамия е преустроена по проект на руския архитект Александър Померанцев, автор на храм-паметника Св. Александър Невски. Разработването и прилагането на плановете е дело на двама български архитекти – Йордан Миланов и Петко Момчилов. Народният поет Иван Вазов не остава очарован от проекта за храма, казвайки:
„Аз не попитах кой е архитектът на тоя нещастен план, но той би заслужил първата премия, ако се даваше такава по конкурс за архитектурно безвкусие.“
Петко Каравелов умира на 24 януари 1903, а на 27 юли същата година, Денят на Св. Седмочисленици, храмът е осветен. Приживе държавникът изразява желанието си да бъде погребан в двора на любимата си църква. Общинският съвет изпълнява волята му, като определя гробът на Петко Каравелов да бъде от северната страна на олтара. Скоро около гроба е изградена каменна балюстрада от черен витошки гранит и е поставена паметна плоча. Съпругата на политика – Екатерина Каравелова, също е погребана на това място след смъртта ѝ през 1947.
В навечерието на Балканската война министърът на правосъдието Петър Абрашев внася законопроект за построяването на Съдебната палата на мястото на стария затвор. Идеята не се приема добре от църковното настоятелство, което има други планове за пространството. През 1912 Столична община решава спора и нарежда затворът да бъде премахнат, а на негово място да бъде създадена градина. Започва постепенното разчистване на терена и в края на 20-те години е премахната и последната сграда от комплекса. Скоро след това е завършена и градината, в която и днес хиляди столичани намират място за почивка.
