Beg ih je najprije pokušao poniziti, a onda su se kršćani dosjetili nečeg nevjerovatnog...
Stara pravoslavna crkva je jedan od najstarijih i najvrjednijih kultuno-historijskih spomenika Sarajeva i ubraja se među najstarije sakralne objekte na ovim prostorima. Nalazi se nedaleko od Baščaršije, na početku Titove ulice.
Crkva s muzejom sagrađena je prije 1539. godine, i više puta je gorjela u požarima koji su pustošili staro Sarajevo.
Današnji izgled dobila je početkom 18. stoljeća. U kompleksu crkve su konak i muzej iz 1890. s bogatom zbirkom ikona, slika, knjiga i rukopisa, kujundžijskih radova, bogato ukrašenih odijela za molitvu i drugih vrijednih eksponata. Stara pravoslavna crkva podignuta je u srcu Baščaršije, na prostoru poznatom kao Stara varoš, nadomak islamskih i vjerskih objekata drugih ovdašnjih religija.
Temelji crkve su u nešto nižem nivou od Baščaršije. Izgrađena je od tesanog kamena u originalnom stilu, koji se ne uklapa u srednjovjekovne srpsko-bizantijske objekte jer ima pravougaonu osnovu i elemente islamske arhitekture. U crkvu su stoljećima s raznih strana svijeta donošene vrijedne relikvije, ali i svetinje. Posebno je bio vrijedan dar patrijarha Arsenija IV Jovanovića, koji je crkvi poklonio mošti sv. Tekle, mučenice iz prvih stoljeća kršćanstva.
No, vjerovatno najzanimljivija stvar vezana za Staru pravoslavnu crkvu je legenda o njenoj izgradnji. Legenda o nastanku crkve kaže da je Gazi Husrev-beg, na molbu sarajevskih pravoslavaca da izgrade crkvu, pristao, uvjetujući da građevina bude jednostavna i da pokriva isključivo prostor onoliki koliko je volovske kože. Neki mudri starac se dosjeti pa izreza kožu na tanke kaiševe, njima označi zemljište i omogući da se sagradi dovoljno velika crkva i da se ispuni sultanov uslov. Gazija prihvati njihovu domišljatost i dozvoli gradnju, pa tako nastade crkva. Opasana je zidom čije dvorište nadahnjuje posjetioca da u mislima odluta nekoliko vijekova unazad. Ljetopisac Mula Mustafa Bašeskija bilježi da je tadašnji namjesnik Bosne Gazi Husrev-beg dao dozvolu za gradnju crkve na molbu svog roba Matijaša.