Emperor Basil I founded the Macedonian dynasty, which historians consider the most successful in Byzantine history. He came to power with a particular self-image: he saw himself as a new Justinian, a restorer of imperial greatness after centuries of decline. Building programs were central to that identity, and the Nea was the crowning project. Its name was not accidental. Calling it the "New Church" implied a new era — Basil's era — and the structure was deliberately designed to echo and rival the Hagia Sophia, the supreme monument of an earlier age. The church was built under Basil's personal supervision in the southeastern corner of the Great Palace complex, near the site of the tzykanistērion, the imperial polo field. It was consecrated on 1 May 880 and dedicated to Jesus Christ, the archangel Michael, the Prophet Elijah, the Virgin Mary, and Saint Nicholas.

Basil was not modest about the decoration. Constantine VII's ekphrasis describes a building encrusted with gold mosaic, colored marble, and precious stones — the interior surfaces blazing with the kind of programmatic richness that Byzantine court art made its signature. To furnish it appropriately, Basil stripped materials from other structures in Constantinople, including the mausoleum of Justinian himself. The atrium before the western entrance held two fountains of marble and porphyry. Porticoes ran along the northern and southern sides. To the east of the complex lay a garden called the mesokēpion — the "middle garden." Most scholars believe the church was built in the cross-in-square form: a central dome over the crossing, with four arms extending outward, a typology that the Nea appears to have helped establish as the dominant form of Middle Byzantine religious architecture.

Along with the Palace oratory of St Stephen and the Church of the Virgin of the Pharos, the Nea was one of the three principal repositories of holy relics in the Byzantine imperial palace — a status that tells you something about how seriously Basil took the building's sacred role. The collection housed there included the sheepskin cloak of the Prophet Elijah (one of Basil's personally favored saints), the table of Abraham at which he hosted three angels according to scripture, the horn that the prophet Samuel used to anoint David, relics of Constantine the Great, and, after the 10th century, the "rod of Moses," transferred from the Chrysotriklinos, the imperial throne room. These were not ornaments. They were the spiritual foundations of imperial authority, concentrated in a building that Basil had made his personal ecclesiastical statement.

The Nea Ekklesia served as a seat of palace ceremony for generations, with the anniversary of its consecration celebrated as a major dynastic feast at least through the reign of Constantine VII in the 10th century. At some point in the late 11th century it became a monastery, known as the New Monastery. The Latin Empire that occupied Constantinople after 1204 continued using the building. It survived through the Palaiologan period — the last dynasty of Byzantium — and was still standing when the Ottomans took the city in 1453. The Ottomans converted it to gunpowder storage. That decision sealed its fate. When lightning struck in 1490, the explosion demolished what six centuries of use and Constantinople's many earthquakes and fires had left intact. The site lies within what is now the gardens south of Topkapı Palace; nothing marks where the Nea stood, and scholars continue to debate its exact footprint.