Of the Byzantine church, the remains of which, surviving ruin, left space to the new ecclesiastical building built by the crusaders, consist in just a few walls on the foundation level, and sections of mosaic flooring. The digs of last century enabled an outline of the building layout: this consisted in a church oriented east to west, preceded by an atrium and flanked to the south by a monastery. Overall, these buildings covered an area of 48 metres in length from west to east, and 27 metres from north to south.
The Byzantine architects integrated natural environments into the church, made up of Grottos: this was not a new feature, in fact many Byzantine churches, such as those of Tabga or Getsemani, housed venerated rocks, or such as the church of Nativity, built around a series of grottos.
The church was made of three naves, the central one closed off by a semicircular apse. The grottos, at least two in number, were incorporated in the northern nave and were on a lower level: this is why the lateral grotto was accessed from the central nave by a stairway. There was a rectangular room at the end of the southern nave, interpreted as being a sacristy. The church exterior was 19.5 metres long and, including the atrium 39.6 metres long. The central nave was 8 metres wide.
The atrium leading to the church covered a large cistern still in use until 1960, and commonly known as the "cistern of the Virgin". Of the monastery there remains a row of rooms, while the area closest
to the church was irretrievably damaged by the crusade buildings.
The most well-known aspect of the Byzantine church is the mosaic flooring, present both on the area of the grottos and in the naves and monastery. Comparisons with a number of mosaics, oriented to the north, rather than the east, leads us to suppose that not all were made for the Byzantine church but were probably the flooring of an older building oriented towards the grottos.
The mosaic of the central nave, already noted during the digs of Father Prospero Viaud, is oriented to the north. It depicts the monogram of Christ on a white background, enclosed in a crown tied at the bottom with two tapes; in the lower section there are a number of crosses, including a great cross, with four small crosses alongside. It is worth noting that tiles of different sizes were used to complete this mosaic.
The mosaic on entrance to the grottos was unearthed by Brother Benedict Vlaminck, while conducting investigations outside the walls of the 18th century crypt. Along the west side of the Grotto of the Annunciation, he found the remains of another frescoed grotto, which had a mosaic on the entrance bearing the inscription in Greek, citing the deacon Conon of Jerusalem, as donor of the mosaic, under the same name of Conon of Nazareth, relative of Jesus and martyr of the 2nd century. This mosaic is also oriented to the north, like the mosaic of the central nave, and depicts a carpet with squares joined by diagonal lines interspersed with diamonds; crosses and other geometrical patters can be seen inside the squares. The inscription is found in a corner of the entrance to the grotto, known as the "Grotto of Conon". In this small grotto, there is a floor with a white background, featuring a larger square joined with diagonal lines to a smaller central square with diamonds alongside, the monogram of Christ is also found here.
The mosaics laid specifically for the Byzantine church are those oriented to the east, which can be seen in the southern lateral nave: there are also traces of the geometrical cornices that framed the entire nave. The oldest mosaic was later covered by a second. The primitive mosaic was with a fish scale frame containing a small flower, to then be replaced by a more elaborate cornice featuring a pattern of circles and diamonds. The elaborate details of this second mosaic distinguish it from all others found.
At the eastern end of the same nave, in the sacristy, there are traces of another mosaic, in the style of the that in the central nave and the grotto of Conon, with squares and diamonds on a white background.
The other areas of the monastery also had mosaic floors, conserved above all in two adjacent rooms, one small and one larger and rectangular. The first features a cornice of intertwined cords; the second shows a cross of flowering branches that form diamonds and an intertwined cornice surmounted by circles, limited to the eastern part of the room. In this larger room, towards the centre, the remains of a clay jug were also found, embedded in the floor.
The most precious feature of these mosaics is the presence of unmistakeably Christian symbols, such as the simple, great and monogram crosses. This element, typical of the Byzantine religious buildings, contributes to establishing the "terminus ad quem", i.e. the time frame within which the flooring was laid, as a decree by Theodosius II, in 427 (Cod.Just. i.8.I), forbade the representation of crosses in flooring.
The closest comparison for the mosaics of Nazareth is found in the church of Shavei Zion of the 5th century, which as well as featuring the cross conserve evident similarities in the geometrical patterns.
The Byzantine church also held a number of architectural fragments found in the digs: for example five pulvinos in white stone decorated at the sides with crosses, probably originally located between Corinthian style capitals and the start of the nave arch. Six high column bases were also unearthed, which probably belonged to the older building. Various other fragments belonged to the balustrade that divided the nave from the presbytery: the small square pillars supported the panels in marble decorated with grape vines, crosses, crowns and inscriptions in Greek, of which some fragments were conserved.
According to Father Bagatti, when considering both the stylistic and architectural features, the Byzantine church can be dated within a vast period, ranging from the 5th century to the 7th-8th century.