The basilica was built at the place of what is known as the cross-shaped Mausoleum, an older religious building that is thought by some researchers to be an unknown kind of Bulgar heathen temple. According to the Shumen architectural museum's research, an early Christian martyrium that included a cross-shaped church and a holy spring also existed at that place. The martyr buried there is thought to be Enravota, the first Bulgarian saint. The martyrium is thought[by whom?] to have been destroyed in 865 during the failed rebellion of the heathens in the wake of the Christianization of Bulgaria. Other researchers,[who?] however, regard the cross-shaped remains as a mausoleum of early Bulgarian rulers.
The archbishop's residence lay to the north and south of the basilica: the northern yard hosted a residential building, with a bath with a hypocaust lay to the west of it. The building to the south of the cathedral accommodated a school and a scriptorium. Two necropoleis are located in the vicinity of the complex: a monastic necropolis lies to the southwest of the church, while a secular one intended for nobles was unearthed in front of the basilica's apse. The yard north of the basilica also accommodated monastic buildings with a kitchen and a dining room. The eastern part of the yard was allocated for a residential building with ten identical monastic cells. Another bath with a hypocaust, a cross-shaped one, and a well lay in the centre of that yard.