'''Nea''' a fost terminată în anul 543 d.Hr., iar construcţia sa a fost înregistrată într-o carte despre clădirile proiectate ale lui Iustinian de către istoricul bizantin Procopius. Biserica a fost proiectată de un arhitect din [[Constantinopol]], pe nume Theodoros. Iustinian a ordonat ca biserica să fie construită pe cel mai înalt deal din Ierusalim şi i-a specificat mărimea. Datorita mărimii bisericii specificată de către Iustinian, aceasta nu a putut fi construită pe pământ. Astfel, partea de sud-est a structurii a fost amplasată pe o fundaţie boltită pe care au fost construite o serie de bazine. O ''tabula ansata'' (tăbliţă de scris) descoperită într-unul dintre bazine l-au asociat pe împăratul ''Flavius Iustinianus'' (Iustinian) cu proiectul care a fost notat şi sub îndrumarea "...prea sfântului Constantin, [[preot]] şi [[egumen]]..." care era [[stareţ]]ul mănăstirii. Procopius a însemnat de asemenea nevoia de extindere a sitului clădirii, care trebuia să mai susţină mănăstirea, un azil şi o bolniţă.

Biserica Sfântului Mormânt, cealaltă biserică importantă din Ierusalim la acea vreme, a fost amplasată mai înspre nord de-a lungul Cardo pe cealaltă parte a acesteia. Aceste două biserici sunt înfăţişate mai pronunţat pe faimoasa hartă mozaică Madaba din Ierusalim care a fost descoperită printre ruinele bisericii bizantine din Madaba, Iordan, în 1884. Această hartă este cea mai veche vedere de ansamblu a Ierusalimului şi arată cu strălucire cele două biserici între care au fost făcute procesiuni.