Bede recorded that Augustine reused a former Roman church. The oldest remains found during excavations beneath the present nave in 1993 were, however, parts of the foundations of an Anglo-Saxon building, which had been constructed across a Roman road. They indicate that the original church consisted of a nave, possibly with a narthex, and side-chapels to the north and south. A smaller subsidiary building was found to the south-west of these foundations. During the 9th or 10th century this church was replaced by a larger structure () with a squared west end. It appears to have had a square central tower. The 11th-century chronicler Eadmer, who had known the Saxon cathedral as a boy, wrote that, in its arrangement, it resembled St Peter's in Rome, indicating that it was of basilican form, with an eastern apse.