Constructed in the fifth century, the Eastern Basilica is one of the oldest churches in the world to be built in the shape of a cross. It was built over an older structure from the first century BCE, which explains why its entrance is to the north: you enter this church from the main road.
An inscription suggests that the older structure was a temple, dedicated to the god Apollo. Perhaps, the pink granite column bases are spolia from this sanctuary. The columns of cipollino marble, on the other hand, were certainly not from the old temple; they were removed from the theater. Originally imported from Euboea during the late first century, they were originally used in the stage wall; after the tidal wave of 365 had made it impossible to use the theater, the columns were reused in this church.
The church used to have some interesting sixth-century mosaics, some of which are now in the museum. Others can be seen in the southern transept and the apse.