Biserica actuală s-a realizat pe fundaţia altei biserici, a cărei piatră de temelie a fost pusă în anul 1835 pe fosta stradă I. Slătineanu (numită aşa în cinstea primului prefect al Brăilei) astăzi strada Ana Aslan, cu banii proveniţi din donaţiile cetăţenilor şi din veniturile Bisericii Vechi. Ea reprezintă a doua biserică ridicată în Brăila după eliberarea de sub turci a oraşului. În realitate este chiar prima, deoarece biserica „Sf. Arhangheli” este o construcţie transformată dintr-o fostă geamie, nefiind construită din temelie. Ea a fost realizată într-un interval scurt de timp, numai un an, astfel că în anul 1836 construcţia era terminată.
Interioarele reprezentând pictura, şi celelalte dotări au fost efectuate până în anul 1839, important fiind însă faptul că Brăila dispunea de al doilea lăcaş nou de cult, aşezat în plin centrul oraşului care era şi cea mai înaltă construcţie din localitate. Din această cauză ea servea pompierilor oraşului drept turn de observaţie pentru incendii. Biserica va fi dotată şi cu o şcoală cu trei săli de clasă ce a fost inaugurată la 7 decembrie 1841, şcoala fiind pentru formarea de învăţători. În 1843 cei trei preoţi care slujeau la biserică se adresează domnitorului Gheorghe Bibescu să le trimită cei 1000 de lei pe care i-a promis bisericii pentru diferite lucrări interioare, cu ocazia trecerii sale prin Brăila.
Biserica, din nefericire a ars în data de 6 octombrie 1859 din cauza neglijenţei unui pompier, incendiul izbucnind în 
clopotniţa ce era şi foişor de foc, şi apoi s-a extins la întreaga construcţie. În acelaşi an preoţii, epitropii şi localnicii, vor începe o acţiune de colectă publică pentru refacerea bisericii, construindu-se actuala clădire. Finalizarea lucrărilor s-a făcut în anul 1865, când a avut loc şi sfinţirea ei. Hramul bisericii a rămas acelaşi: „Sfântul Nicolae”.
Arhitectul construcţiei nu se cunoaşte, dar biserica are planul în formă de navă cu altarul semirotund stilul arhitectonic fiind reprezentat de un amestec de elemente bizantine şi gotice. Dimensiunea interioară este de 37 m, lungime 10, 50 m lăţime şi 20 m înălţime. De menţionat că la înălţimea actuală s-a ajuns în urma unor reparaţii radicale care a avut loc în anul 1899 când i s-a făcut o nouă cupolă şi i s-a înălţat acoperişul cu şase metri.
În perioada de până la primul război mondial, biserica avea o avere de 50 000 lei, dispunând de două clădiri şi două terenuri în oraş. Pictura este renascentistă fiind realizată de către pictorul Petre Alexandrescu în etapa 1888 – 1900 şi restaurată între 
1928 – 1932 prin eforturile brăilenilor.
Încă din secolul al XIX -lea ea a fost declarată catedrala oraşului, aici efectuându-se principalele festivităţi civile şi religioase. După 1990 a revenit la acelaşi rang şi datorită proclamării la 6 decembrie 1993 a Sfântului Mare Ierarh Nicolae, ocrotitorul corăbierilor foarte numeroşi în portul Brăila, drept patron al oraşului fapt pentru care anual se organizează mari festivităţi.
Biserica este dotată astăzi cu un cabinet medical situat în strada Ana Aslan nr .12, şi este deservită de doi preoţi : Preotul Paroh Leontin Popescu ajutat de preotul pensionar Costică Creţu.
Biserica se află pe strada Ana Aslan nr. 12.
Sursa : „Bisericile Brăilei ” Dr. Ionel Ştefan Alexandru