Von besonderer Bedeutung war jedoch eine Entdeckung in der Nordwestecke der Grabungsfläche. Unter Abbruchschichten des 16. Jahrhunderts tauchten einzelne Steine eines Fundamentes auf, dessen Ausbruchgrube sich fortsetzte und sich schließlich als Teil der Hauptapsis und der südlichen Seitenapsis eines großen Kirchenbaus erwies. Hierbei kann es sich nur um die Überreste der Kirche des Augustiner-Chorherrenstiftes Neuwerk handeln, das sich im Mittelalter an der Stelle des heutigen Botanischen Gartens erhob. Damit konnten erstmals Spuren der Klosterkirche Neuwerk zweifelsfrei identifiziert werden, deren Standort seit nahezu 500 Jahren verschollen war – eine archäologische Sensation.

Auch wenn die erhaltenen Überreste der Klosterkirche auf den ersten Blick bescheiden wirken, so lassen sie durch den Vergleich mit heute noch stehenden Kirchen der Augustiner-Chorherren wie der Liebfrauenkirche in Halberstadt oder der Stiftskirche St. Pankratius in Hamsleben (Landkreis Börde) auf einen Bau von beeindruckender Größe schließen. Über die Gestalt der Kirche lassen sich darüber hinaus nur wenige Aussagen treffen. In der Chronik des Johann Christoph von Dreyhaupt aus dem 18. Jahrhundert ist das Propstsiegel des Klosters Neuwerk abgebildet, das eine Kirche mit vier Türmen zeigt. In einem Bericht über den Abriss des Klosters im 16. Jahrhundert ist ebenfalls von vier zum Einsturz gebrachten Türmen die Rede, sodass diese Information wohl verlässlich ist. Daneben berichtet der hallische Ratsmeister Markus Spittendorf im Jahr 1476, dass weder Langhaus noch Chor überwölbt waren. Beide besaßen dem Bericht zufolge lediglich eine Decke aus bemalten Holzbrettern, die jedoch so morsch waren, dass während eines Gottesdiensts ein Junge durch die Decke brach und zu Tode stürzte. Ob daraufhin eine Einwölbung der Kirche folgte, ist nicht bekannt.

Der Standort des Augustiner-Chorherrenstifts in topografisch exklusiver Lage zwischen Halle und Giebichenstein, an der strategisch bedeutenden Heer- und Handelsstraße nach Magdeburg, war der 1167 aufgezeichneten Gründungslegende des Klosters nach nicht zufällig gewählt. Ihr zufolge befand sich ein Bürger Halles namens Hazecho im Jahr 1116 auf dem Rückweg von der Burg Giebichenstein, wo er mit dem Magdeburger Erzbischof Adelgot verhandelt hatte, als er Zeuge eines wundersamen Zeichens wurde: Vom Himmel sank eine Egge in Flammengestalt herab. Vor den Augen des rasch herbeigeholten Erzbischofs fuhr sie wieder in den Himmel auf. Adelgot ließ an der durch das göttliche Zeichen gekennzeichneten Stelle das wohl ohnehin geplante neue Kloster errichten. In einer dort im Jahr 1121 ausgestellten Urkunde wird die Errichtung des Klosters bestätigt und der Neubau einer Basilika zu Ehren der Jungfrau Maria erwähnt. Im Laufe des 13. Jahrhunderts kamen der Evangelist Johannes und der Märtyrer Alexander als Schutzheilige des Klosters hinzu. Der Reliquienschrein mit den Gebeinen des Heiligen Alexander, die sich seit 1124 im Kloster befanden, gehörte später offenbar zu den wichtigsten Schätzen des Halleschen Heiltums, der heute nahezu vollständig verlorenen bedeutenden Reliquiensammlung Kardinal Albrechts. Dieser führte das Kloster Neuwerk 1528 mit seinem Neuen Stift zusammen und beraubte es damit vollends seiner Eigenständigkeit. Mit der Auflösung des Klosters 1530 ging schließlich dessen gesamtes Vermögen auf das Neue Stift über. Dieses war beträchtlich: Bereits 1121 war das Kloster zum Neuen Werk mit privilegierten Markt- und Zollrechten ausgestattet und verfügte über umfangreichen Besitz an Land, Mühlen und Pfarrrechten. Zur Zeit Kardinal Albrechts galt es als das mächtigste und wohlhabendste Kloster im Süden des Erzbistums Magdeburg. Daneben war es ein bedeutender Ort der Gelehrsamkeit und Glaubensvermittlung. Mit seinem 1144 verstorbenen Propst Lambert hatte es sogar einen Heiligen hervorgebracht, dessen Anrufung Wunder bewirkt haben soll.