Biserica a fost construita la sfirsitul secolului XVII - inceputul secolului XVIII, spun istoricii - pe vremea domnitorului Constantin Brancoveanu -, in vecinatatea redutelor turcesti ce aparau citadela. Trebuie precizat faptul ca, desi s-au aflat sub administratie otomana aproape trei secole (1540 - 1828), crestinii din Braila s-au inchinat liberi Mintuitorului. Aici s-a aflat vechea Mitropolie a Proilaviei. Se spune ca, la 1828, in urbea dunareana existau deja trei biserici crestine, cu carti de slujba tiparite in greceste, la Venetia. Dupa plecarea administratiei otomane, marele duce Mihail Romanov, conducatorul ostilor rusesti biruitoare, a hotarit darimarea citadelei (fortului) si transformarea geamiei din actuala Piata Traian (fosta "Sfintii Arhangheli", fosta "Dumitru Ionescu") in biserica crestina. Trei mii de salahori, spun documentele, au muncit timp de trei ani ca sa faca una cu pamintul vechea fortareata. La ora actuala, numai hrubele ce impinzesc Centrul Vechi mai amintesc de turci.
In anul 1831, fosta casa de rugaciune turceasca a devenit biserica cu hramul "Sfintul Arhanghel Mihail", dupa numele printului Romanov. Binefacatorul a impodobit sfintul lacas cu icoane si carti de cult. Icoana Sfintului Mihail, imbracata in aur si argint - realizata in Rusia si donata bisericii in anul 1834, de marele duce -, poate fi admirata si astazi, in dreapta catapeteazmei. Biserica a avut nevoie de nenumarate lucrari de consolidare, intrucit a fost ridicata de catre turci din caramida nearsa si pe sol instabil, fiind afectata, deopotriva, de cutremure si umiditate. In anul 1883, a ars clopotnita din lemn a sfintului lacas, fiind atunci distruse si cele trei clopote de bronz turnate la Sankt Petersburg, in anul 1832. Clopotnita actuala, precum si clopotele, au fost realizate pe cheltuiala sotilor Nedelcu si Ana Chercea, mari filantropi, in anul 1922. Alte lucrari importante de consolidare s-au realizat in anii 1935 si 1966.
Dumnezeu a scapat biserica "Sfintul Mihail" de la demolare, in anii prigoanei comuniste. Incercarile autoritatilor atee din anii '50 au esuat lamentabil datorita preotului paroh Alexandru Mateescu, devotat slujitor al altarului, trecut acum la Domnul. Ctitoria din Centrul Vechi a fost restaurata intre anii 1995 - 2000, cu sprijinul Ministerului Culturii si Cultelor. Cu acest prilej, in zona au fost efectuate ample investigatii arheologice, coordonate de prof. univ. dr. Ionel Candea, directorul Muzeului Brailei. Istoricul a reusit sa descopere printre altele o necropola crestina din veacul XV, cu aproape 50 de morminte de inhumatie, dovedind astfel ca biserica este ridicata pe un vechi de aproape sase sute de ani.