The Church was discovered after 1300 years by modern archaeologists, based on a 6th century (AD) map called the Madaba Mosaic Map! Till date, Madaba Map is the oldest known map of Jerusalem. It was discovered in 1894 as the floor of a 6th century Byzantine church from Jordan. Ever since the discovery of Madaba Mosaic, the map had become a precious tool for archaeologists to discover some very important ancient monuments in Jerusalem. Never had archaeologists any clue for the existence of such a magnificent Church in Jerusalem before the discovery of Madaba Mosaic. Since, the map has yielded some vital information for rediscovering ancient structures; its authenticity has been generally accepted. The quest had a final outcome in 1970s, when the late Israeli archaeologist Avigad Nahman rediscovered the Nea Church almost 1300 years later, exactly at the same spot where Madaba Map marks the Church.
The largest church ever constructed in Jerusalem, the Nea, was an impressive engineering feat. Built as a standard Roman basilica with four rows of pillars, a nave with two to four side aisles; the complex also had a monastery and hospital with 3000 beds for the sick. When the monument was designed, the southern end of the Church was to rest on a slanting hill. In other words, on one side, the church has to be built on a solid rock and on the other it should be suspended in the air. As the ground level was much below the hill, huge underground vaults, nearly 35 feet high, were needed to support a platform on which the Church was constructed. These vaults formed a massive cistern (33 x 17 m) with a capacity for thousands of liters of water. Today, this massive cistern and two apses of the original Nea Church have been unearthed.
From the walls of the cistern a Greek dedicatory inscription was discovered in 1977, identifying this as the work of Justinian and even mentioning the exact date of construction. The reading goes as:"And this is the work which our most pious Emperor Flavius Justinian carried out with munificence, under the care and devotion of the most holy Constantine, priest and Hegumen, in the 13th (year of the) indiction"(549/550 AD). The discovery put an end to the much debated question if the identified site is Nea Church itself.
Just a few comments to add: It took me more than five trips to Jerusalem to even locate the coveted site. For me least, all the online maps and guide books were not helpful to pinpoint the location. Thanks to the directions provided in Jerome Murphy O'Connor's classic "The Holy Land: An Oxford Archaeological Guide", which ultimately guided me to the remains of the Church, deep inside the Jewish Quarter. Although it took quite a long time to find the Church, I had the opportunity to learn more about some rare archaeological sites nearby. I am still clueless if I have seen all the excavations from Nea Church, but for sure the Church will remain special among my adventures in Jerusalem.