Prima atestare documentară a unei biserici ortodoxe în Brașov apare într-o indulgență emisă de Papa Bonifaciu al IX-lea, în anul 1399, în care se vorbește despre "schismaticii ortodocși".
Pe locul bisericii "Sf. Nicolae" din Scheii Brașovului, cercetările arheologice au confirmat existența succesivă a trei edificii de cult, începând cu veacul al XIV-lea. Cea dintâi a fost o biserică de lemn.
Se pare însă că prima biserică de zid din Șcheii Brașovului a fost construită începând din anul 1495, cu acordul magistratului din Brașov, iar șantierul a durat aproape un secol.
Primul ctitor important al bisericii Sfântul Nicolae din Șcheii Brașovului, cel mai reprezentativ lăcaș de cult ortodox din Țara Bârsei, a fost domnitorul muntean Vlad Călugărul, deşi tradiția, potrivit cronicarului brașovean Radu Tempea II, l-a reținut pe domnitorul Neagoe Basarab, care într-adevăr, după câțiva ani, a trimis pe șantierul din Şchei "daruri bogate şi mulți meșteri lucrători".
În 1583, domnitorul Munteniei, Petru Cercel a sprijinit lucrările de mărire a bisericii. Apoi, domnitorul Moldovei, Aron Vodă, a sprijinit finalizarea lucrărilor la biserică în 1594, printr-o danie cu care s-a supraînălțat turnul şi "s-a zugrăvit biserica şi pe dinlăuntru şi pe dinafară cu mulțime de istorii ale sfinților".
În 1733 au fost puse temeliile paraclisului de nord, datorită daniei domniței Ancuța, fiica voievodului Constantin Brâncoveanu. Purtând hramul "Bunei Vestiri", noul paraclis a fost pictat între anii 1735-1738. Cel de al doilea paraclis, ridicat spre sud, cu hramul "Înălțarea Domnului", a fost terminat în anul 1750, având sprijinul unor negustori locali.
Biserica a fost renovată în perioada interbelică. Interiorul bisericii centrale a fost pictat de Costin Petrescu, în anii 1940. Pe peretele dinspre miază-noapte a fost pictată intrarea domnitorului Mihai Viteazul în Brașov, iar pe peretele de sud scena încoronării regelui României Mari, Ferdinand I, la Alba Iulia.