Il est possible que la crypte contiennent des vestiges d'une église paléochrétienne, sans doute située hors des murs de la ville, dédiée à sainte Marie, dont l'existence remonterait au VIesiècle, et attestée par une lettre du pape Grégoire Ier. C'est au cours de travaux d'agrandissement, en 1094, qu'un sarcophage en marbre avec une petite croix en or sur laquelle est gravé le nom Cataldus y ont été trouvé. Cette croix est aujourd'hui conservée parmi les trésors de la cathédrale. Les travaux se poursuivirent avec la reconstruction de la crypte, avec un schéma à trois bras du transept supérieur et du chœur, et la construction d'une chapelle destinée à accueillir les ossements du saint, accessible depuis le transept nord[1].
L'église actuelle, initialement dédiée à sainte Marie Madeleine, fut construite par les Byzantins dans la seconde moitié du Xesiècle, lors des travaux de reconstruction de la ville ordonnés par l'empereur Nicéphore II Phocas, à la suite du pillage de la ville par les Sarrasins en 927, lorsque les musulmans détruisirent définitivement ce qui restait de l'ancienne ville gréco-romaine.
En 967, après quarante ans, l'empereur byzantin, considéré comme le deuxième fondateur de Tarente, s'intéressa à la cité et décida de la reconstruire, en édifiant l'actuelle vieille ville, à partir précisément de la construction de la cathédrale. Lors de cette opération, les derniers vestiges de la ville antique et de l'acropole disparurent. La cathédrale et sa crypte ont en effet été construites avec des matériaux de récupération provenant des constructions précédentes, typiquement grecques et romaines. On remarque en effet que les colonnes de la cathédrale sont toutes différentes les unes des autres.
Au cours des dernières années du XIesiècle, l'édifice byzantin fut remanié et la cathédrale actuelle, de plan basilical, fut construite à l'époque normande. Cependant, l'ancienne construction ne fut pas entièrement remplacée: le bras longitudinal, agrandi et abaissé, incorpora la nef centrale avec la profonde abside de l'église byzantine, qui resta inchangée; l'autel est placé sous la coupole et l'ancienne nef est devenue le transept, coupé ensuite par les nefs latérales, laissant apparaître une série de colonnes qui ornaient l'ancienne construction. En 1713, la façadebaroque, œuvre de l'architecte Mauro Manieri de Lecce, a été ajoutée.