Biserica Sfânta Maria, cu hramurile „Nașterea Maicii Domnului" (8 septembrie) și „Sfântul Nicolae de vară" (9 mai), este prima biserică ridicată în Constanța după Revoluția din decembrie 1989. Preotul Voicu Neculai, în calitate de paroh al Parohiei Sf. Nicolae-Vechi din Constanța (din anul 1987), s-a implicat în dobândirea unui teren pe Bulevardul 1 Mai în vederea construirii acestui sfânt locaș de cult creștin-ortodox.
Prin Decizia Primăriei Constanța, în anul 1990, s-a transmis în administrarea Parohiei Sf. Nicolae-Vechi un teren situat în Constanța, Bulevardul 1 Mai, nr. 21. Parohia Sfânta Maria s-a înființat ca entitate bisericească și juridică la 1 ianuarie 1994.
Lucrările de construire au început în luna mai 1990 și s-au încheiat în toamna anului 1997. În data de 7 decembrie 1997 a avut loc slujba de sfințire, săvârșită de către IPS Lucian Florea, Arhiepiscopul Tomisului. Biserica a fost construită sub formă de cruce, cu trei turle, păstrând până azi zidăria de cărămidă.
Lucrările de pictură au demarat în anul 2004 și s-au finalizat în 2008, fiind realizate de Arhid. Aureliu Voicu. În ziua de 9 noiembrie 2008, IPS Dr. Teodosie Petrescu, Arhiepiscopul Tomisului, a săvârșit slujba de sfințire a picturii.
Parohia deține o clopotniță, un lumânărar și o capelă folosită inițial ca spațiu liturgic. În această construcție sunt încorporate astăzi: bucătăria, trapeza (sală pentru parastase, capacitate 60 locuri) și capela mortuară.
În data de 5 ianuarie 2014 a fost sfințită troița din curtea bisericii de către IPS Dr. Teodosie Petrescu — donația unor credincioși vrednici ai parohiei.
Prin osteneala pr. Nicolae Popescu au fost aduse părticele din Sfintele moaște ale Sfântului Ioan Botezătorul, ale Sfântului Sfințit Mucenic Haralambie, ale Sfântului Ierarh Nectarie, precum și o părticică din Lemnul Sfintei Cruci. În Postul Sfintelor Paști 2014, IPS Dr. Teodosie a oficiat slujba de așezare în raclă a Sfintelor Moaște.
În perioada 8–10 septembrie 2017, a fost adus spre închinare „Brâul Maicii Domnului" de la „Mănăstirea Kato-Xenia", situată la 50 km de Volos, Grecia.
Astăzi, prin proiectul „Să oferim împreună o masă caldă celor în nevoie", parohia oferă în fiecare duminică, după Sfânta Liturghie, hrană celor aflați în nevoie. Biblioteca parohială păstrează numeroase cărți cu caracter duhovnicesc, la dispoziția tuturor.