Черквата е градена през 1602 г. В местността Аязмото в клоните на един бряст
неизвестен българин открил икона. Неясно е как се е озовала там, но
това било чудотворна икона, тъй като не се крепяла на клоните, а висяла
във въздуха. Хората се решили да я снемат и занесат във Варна. И сега
станало чудо, когато воловете на случайно минаващ турчин, на чиято кола
натоварили иконата, отказали да тръгнат. Същото се повторило и с миналия
покрай тях грък. Накрая иконата била пренесена от млад българин.
Впечатлени от чудото хората решили, че където спрат воловете на българчето там ще построят черква. Случило се до площада в тогавашния център на града. По време на робството всички християнски храмове се градели почти тихомълком и така, че да не бият на очи. Не можели да са над два метра и това е причината храмът да е вкопан ниско в земята. По време на строителството се оказало, че и в миналото тук е имало малка черква. Първоначално основният кораб бил широк седем метра и дълъг осем метра. През 1640 г. след пожар черквата е възстановена и разширена, като с годините се оформя сегашния й вид. До 1914 г. тя е под опеката на гръцката митрополия, след това е затворена за десетина години, а през 1924 г., след идването на българския й настоятел е отворена отново.
Особено интересен е иконостасът на "Малката Света Богородица". Според историческите данни той е направен през 1896 г. Изработен е от тъмно дърво, вероятно орех или кипарис, наситен с православни символи и богато орнаментиран. За съжаление майсторът на този шедьовър е неизвестен, но рисунъкът напомня дебърската школа.
Иконите в черквата са истинско съкровище и малко храмове могат да се похвалят с такова богатство, твърдят експерти. Единственото противоречие с църковните предписания е, че повечето ликове на светците гледат на юг, а не на запад. Легендата разказва, че когато за пръв пат донесли иконата на св. Богородица Чудотворна я поставили на източната страна. Сутринта, незнайно как тя била на северната. Това се повторило няколко пъти, докато накрая миряните решили да я оставят там, където я отнася провидението. Миряните приели да нарушат канона, но не и божията воля.
В описанието си на турските укрепления братя Шкорпил изказват мнението, че тук би могъл да бъде гробът на Владислав Варненчик. Те правят този извод от показанията на Х.Мергест, който бил пленен по време на сражението от 1444 г., и според когото кралят бил погребан в една малка черквица. "Света Богородица Панагия" била най-старата черква във Варна и по времето на Шкорпил, от което вероятно идва и този извод.