In seguito al crollo dell'impero Romano, Olbia fu invasa dai Vandali: condannarono la città, che era già in piena decadenza, la incendiarono intorno al 450 d.c. Il popolo si rifugiò a Fausania, forse in periferia di Olbia Romana, che si ingrandì d'importanza soprattutto nell'età bizantina: infatti, in una sua lettera, Papa Gregorio Magno dava il proprio assenso alla nomina di un vescovo. Fu dunque sede di diocesi e, probabilmente, anche sede dei primi Giudicati di Gallura, ma, nonostante questo, non rimane alcuna traccia del borgo. Ad Olbia era quindi sovravvissuto un piccolo villaggio, che però si ingrandì nuovamente d'importanza per il rinnovato sviluppo del commercio con la penisola italiana verso lanno 1000: le potenza marinare di Pisa e Genova ne determinarono il rifiorire grazie ai loro traffici commerciali.

Assunto il nome di Civita la città divenne capitale del Giudicato di Gallura e in questo periodo rimase sotto l'influenza di Pisa.

Il primo giudice, di cui si hanno notizie, è Costantino (1073), al quale seguirono Torchitorio (1112), Soltaro e Ottocorre di Gunale, Comita Spano, Costantino e Barisone di Lacon.

A questi giudici si fa risalire la costruzionede vari castelli a protezione dell'abitato, ed una riorganizzazione dei rapporti commerciali, destinata a restituire alla città gli antichi splendori. Soprattutto Pisa risultò favorita da questo sviluppo e rafforzò così la propria influenza sulla Sardegna Nord-Occidentale ma, le successive guerre giudicali avrebbero rovinato questa ripresa.

Olbia rimase a Pisa e assunse il nome di Terranova Pausania (in ricordo di Fausania Bizantina) mantenendolo fino al 1939, anno in cui fu restituito l'antico nome romano col quale oggi è conosciuta. Sotto il governo pisano non si fermò lo sviluppo economico e demografico: il porto tornò ad essere molto importante e rifiorirono le zone interne dell'agro che videro crescere gli insediamenti rurali.

Il Giudicato di Gallura rimase in piedi fino al 1300. lo sbarco degli Aragonesi, che conquistarono tutta l'isola, pose fine ad un periodo splendido della storia di Olbia