Kostel Matky Boží je kamenný pravoslavný kostel postavený knížetem Mstislavem Vladimirovičem v Tmutarakanu v roce 1022.
Podle Příběhu minulých let byl kostel založen na počest vítězství Mstislava Vladimiroviče nad Kasogy a kasogským princem Rededeyem . V roce 1066 zde byl pohřben kníže Rostislav Vladimirovič . Nápis na kameni Tmutarakan je zjevně spojen s kostelem Panny Marie a vypráví o měření vzdálenosti z Tmutarakanu do Korčeva ( Kerč ) v roce 1068. Podle vědců uvedená vzdálenost přesně odpovídá vzdálenosti od kostela Panny Marie ke kostelu sv. Jana Křtitele v Kerchu.
V roce 1955 při vykopávkách Tmutarakan expedice vedená B. A. Rybakovem odkryla zbytky malého kostela se základem 16,5 x 10,4 m. Technologie pro vytvoření základu je podobná technologii použité při stavbě kostela sv. desátky v Kyjevě . Soudě podle tvaru příkopů měl kostel tři apsidy , tvořící třílaločný obrys. Přes budovu procházely tři pásové základy, což dalo důvod se domnívat, že kostel byl šestisloupový (nebo čtyřsloupový s narthexem ). Šířka vnějších základů je 1,5–1,7 m. Zdivo objektu je tvořeno kameny různého druhu (vápenec, mušlí, dlažební kostky) na roztoku vápna s drcenou mušlí; základ tvoří vápencové řady, které se střídají s vrstvami dubových loží vyplněných maltou. Severozápadně od kostela byly objeveny zbytky zcela zdevastovaného kostelního hřbitova.
S výjimkou skromných nálezů naznačujících existenci raně středověké baziliky v Hermonasse je kostel Panny Marie jediným objeveným kostelem na území hradiště.