L’arcidiocesi è il risultato dell’unione di tre diocesi medievali: Turris, Ploaghe e Sorres.
La prima evangelizzazione di Turris Libisonis (Libyssonis), oggi Porto Torres, si deve a persone legate alla navigazione, provenienti per lo più da Ostia, dove è attestata la presenza di negotiatores e navicularii turritani. La recensione più antica del martirologio geronimiano attesta che a Turris, durante la persecuzione di Diocleziano, Gavino subì il martirio il 25 ottobre. La tradizione associa a Gavino anche i martiri Proto, presbitero, e Gianuario, diacono.
La prima menzione della sede di Turris risale al periodo in cui la Sardegna era sotto il dominio dei vandali. Per promuovere la dottrina ariana tra i vescovi cattolici del suo regno, il re Unnerico nel 484 li convocò a Cartagine per una disputa teologica. Vi partecipò anche Felice di Turris insieme ad altri quattro vescovi sardi.
La diocesi in questo periodo risulta suffraganea del metropolita di Carales. Anche nel primo periodo bizantino l’organizzazione religiosa rimase immutata. Infatti dall’epistolario di san Gregorio Magno si evince che il vescovo di Turris, Mariniano, è ancora sotto la giurisdizione cagliaritana. Papa Giovanni V (685-686) contestò, però, all’arcivescovo di Cagliari, il diritto di consacrare i vescovi di Turris, per cui riunì un “concilium sacerdotum”, per farvi dichiarare la diretta dipendenza di quel vescovo dalla Sede pontificia.