La Chiesa di Santa Restituta, sorge sopra la Cripta omonima dedicata alla Santa martirizzata. Venne costruita nel XVII secolo in stile barocco, durante il periodo di contesa del titolo di Primate di Sardegna e Corsica, dei due Arcivescovi di Cagliari e Sassari. Si presenta con una facciata semplice, con un portale sormontato da un timpano. L'interno è caratterizzato dalla volta a botte e da un'unica navata con sei cappelle. Rimase gravemente danneggiata durante i bombardamenti della seconda guerra mondiale. Un primo restauro venne a compimento negli anni '60, un secondo invece è stato effettuato negli scorsi anni.
La Cripta sottostante, ha una storia lunga secoli. Risale infatti al III secolo a.C. ed è costituita da una grotta in parte naturale e in parte scavata dall'uomo, con diversi ambienti. Utilizzata dai punici, dai bizantini e dai romani, costituì per quest'ultimi una chiesa rupestre, come dimostrano i ritrovamenti archeologici, tra cui un dipinto di San Giovanni Battista. Nel XIII secolo, divenne sede di culto alla Santa Restituta, i cui resti vennero trovati all'interno di un urna di terracotta intorno al '600. Si dice che le spoglie vennero portate qui dall'Africa, e un ritratto in marmo raffigurante la Santa, ritrovato sempre nel '600, pare avvallare questa tesi, anche se c'è chi ancora non concorda e ritiene che la Santa sia stata martirizzata all'interno della grotta, divenuta per lei luogo di prigionia.
All'interno della Cripta vi è un altare con tre nicchie scavate nella roccia, al centro delle quali è posto un reliquiario che conteneva la statua della Santa; ai suoi lati invece vi era lo spazio per le statue di Sant'Eusebio e Sant'Eusebia, considerati da alcuni i figli della Santa. Inoltre è ancora ben visibile la colonna del martirio. Intorno al 1620 tutto l'ambiente venne decorato e affrescato, costruendo un grande altare e ornando la cappella con un grande arco impreziosito da foroni e punte di diamante.
Durante il conflitto mondiale la Cripta trovò impiego come rifugio antiaereo e le reliquie vennero spostate al sicuro nelle sale della vicina Chiesa di Sant'Anna, ove rimasero sino al 1997. Nel muro fuori dalla grotta, una lapide ricorda uno dei tragici bombardamenti che colpirono la città e sotto il quale persero la vita numerose persone proprio mentre andavano a ripararsi nella grotta. Al termine del bombardamento, lo scenario apertosi davanti agli occhi di usciva dalla grotta fu davvero straziante.
