The aim of this paper is to present new archaeological data coming from the recent excavations in Adulis (Eritrea) in the so-called “Church of the British Museum”, discovered in 1868 by Captain Goodfellow. New excavations that began in 2018 have led to highlight the biggest church known so far in Adulis, probably the ecclesia episcopalis. It stands as a 30 meters long building, which follows the typical Aksumite architectural layout. Also, the great quantity of decorated marbles coming from the church are of great interest, revealing important contacts with Yemen and Byzantium, mostly in the 6th century AD. The new archaeological data will be contextualized in the wider scenario of the rise and establishment of early Christianity in the Aksumite kingdom, until the arrival of Islam.