No século VII, os muçulmanos sob o Califa Moáuia I saquearam Euceta e destruíram a Igreja de São Teodoro. No século X, a igreja foi reconstruída e Euceta foi renomeada para Teodorópolis. No século XI, os sunitas seljúcidas finalmente dominaram a região, e o jugo muçulmano nunca mais chegou ao fim.

Já no século XIII, durante o Cerco de Constantinopla de 1204, as relíquias de São Teodoro foram saqueadas pelos cruzados e postas numa embarcação com destino a Veneza, no litoral norte da Itália. Entretanto, assim que o navio adentrou o Mar Adriático, ficou parado na costa de Bríndisi na Apúlia (litoral sudeste), e correnteza nem vento conseguiam fazê-lo continuar viagem. O navio só pode seguir viagem após deixarem as relíquias num bote. As ondas levaram-no até a costa da cidade, e um grupo de pescadores descobriu as relíquias. Em seguida, ficaram em uma das catedrais de Bríndisi até o século XVIII.