La Cattedrale fu costruita dai pisani in forme gotico-romaniche tra il 1217 e il 1258. La chiesa originaria aveva forma rettangolare a tre navate, con volta a crociera sulle due navate laterali e copertura in legno della navata centrale ed era dedicata, come la cattedrale di Pisa, a Santa Maria Assunta.

Nel 1258, dopo la distruzione da parte dei pisani della Cattedrale di Santa Cecilia, la chiesa fu elevata a cattedrale della città, affiancando il culto a Santa Cecilia nell'intitolazione. Nello stesso anno venne iniziata la realizzazione del transetto, che rese la pianta della chiesa a forma di croce latina, e le relative due porte laterali. Sulla facciata venne inoltre aperta una bifora gotica e vennero eseguiti interventi sul campanile. Con la conquista di Cagliari da parte degli aragonesi venne completato il transetto destro ed edificate altre cappelle, delle quali solo quella della "Sacra Spina" (detta anche "Cappella Aragonese") è rimasta intatta.

Nel 1614 l'arcivescovo spagnolo Francisco Desquivel fece rialzare il presbiterio per costruire il Santuario dei Martiri. Il 22 novembre 1669 (giorno della festa di Santa Cecilia) un altro vescovo spagnolo, Pietro de Vico, ordinò di rifare gli interni e la facciata in stile Barocco, affidando la direzione dei lavori a Domenico Spotorno. La ristrutturazione, che durò fino al 1704, cancellò quasi completamente la primitiva chiesa romanica: nel 1702 la facciata fu rifatta dall'architetto Pietro Fossati in stile barocco, il pavimento venne sostituito con tarsie marmoree, pilastri calcarei presero il posto delle colonne romaniche, all'incrocio tra la navata centrale ed il transetto venne edificata la cupola e le cappelle gotiche del transetto vennero murate. Al loro posto vennero edificati i monumenti funebri degli arcivescovi Machin e La Cabra.

Nei primi anni del '900, in seguito al distacco di alcuni elementi marmorei, la facciata barocca fu demolita, anche nell'assurda speranza di ritrovarvi sotto l'antica facciata romanica. La Cattedrale rimase circa 20 anni priva di facciata, finché, nel 1933 venne edificata l'attuale facciata neoromanica in stile pisano-lucchese utilizzando pietra calcare del colle di Bonaria e frammenti scultorei della chiesa originaria. Il progetto venne attuato su disegno dell'architetto Francesco Giarrizzo. Nel 1999 è stato effettuato un restauro della cupola, del tetto e del campanile.