Clădirea, inițial o biserică romano-catolică era denumită Biserica Sfintei Maria, înlocuind o clădire mai veche folosită în același scop.
Construirea sa a început la sfârșitul secolului al XIV-lea, la o dată necunoscută – analiza unor dovezi indirecte de către mai mulți cercetători ducând la concluzia că aceasta a început între 1383 și 1385.
Este cunoscut că, în primele etapes, la biserică slujea un perot numit Thomas (decedat în 1410), a cărui mormânt este localizat în zona corului.
Lucrul la fortificațiile din zona înconjurătoare au început probabil în același timp cu lucrul la biserică, ducând în timp la construirea unei a treia cetăți în Brașov.
Navele au fost construite într-un timp mai lung, și construcția a fost întreruptă pentru diverse perioade de timp: în 1423, Papa Martin V a emis o indulgență pentru oamenii implicați în construirea bisericii, ca un mijloc de reactivare a șantierului; în 1474, un document emis de Sixtus IV admitea că lucrările încă trenau.
Mai mulți stâlpi octogonali, refăcuți cel puțin o dată în timpul construirii, au fost probabil terminați în jurul anului 1444.
Unul dintre aceștia prezintă emblema conducătorului militar Iancu de Hunedoara, care este menționat printre ctitorii bisericii.
Cel mai intens s-a lucrat înainte și după 1450, și a implicat terminarea unui număr enorm de prtaluri, incluzând „Poarta de Aur” din partea nordică și altarul adiacent al Sacrificului Sfânt.
Portalul estic, comandat de Regele Ungariei Matei Corvin, a fost terminat în 1476.
Sacristia a fost mărită cândva între 1500 și 1515.