Biserica poartă acest nume datorită icoanei Sfintei Fecioare Maria, găsite în secolul al XVII-lea într-un dud, aflat chiar pe locul unde a fost ridicată. A fost construită (în stil brâncovenesc) între anii 1758-1760, pe locul unei vechi bisericuţe din lemn (ce data din 1700), de către marele clucer Constantin Fotescu şi tăbăcarul Hagi Ion Gheorghe. Înzestrată de ctitori cu mai multe moşii şi prăvălii, biserica a adăpostit în chiliile sale primul spital de alienaţi mintal din regiune. În 1841, a fost demolată (după cutremurul din 1838 se ruinase complet), iar între 1842-1844, a fost refăcută în stilul barocului austriac de către un arhitect vienez, adus de boierul Iordache Otetelişanu. Devenit neîncăpător, sfântul locaş a fost dărâmat în 1913, în locul său fiind ridicată actuala biserică, zidită în stil neo-bizantin după planurile arhitecţilor Ion Trojănescu (Traianescu) şi Sterie Becu (sfinţită în 1942). Este unul dintre locaşurile religioase însemnate ale Craiovei şi a avut un important rol cultural şi filantropic de-a lungul timpului. Din 1992, este catedrală episcopală.