Nel 1071, guidati dal Gran Conte Ruggero, i Normanni occuparono Catania, non senza patteggiare, sembra, con l'emiro di Siracusa, Ibn al-Werd. Era l'inizio di una nuova vita. Ma, partito Ruggero, i Catanesi richiamarono l'emiro, e i Normanni dovettero riconquistare la città nel 1081. I nuovi signori dubitavano della fedeltà di queste popolazioni, che per lingua e cultura oscillavano tra la greco-bizantina e la saracena; per non parlare della consistente comunità ebraica esistente a Catania. Né maggiore fiducia ispirava la gerarchia della Chiesa, nella misura in cui questa poteva essere sopravvissuta alla dominazione araba.
Come per altre parti della Sicilia, Ruggero preferì dunque creare una struttura civile ed ecclesiastica integralmente nuova, affidando ai monaci benedettini la direzione dell'evangelizzazione religiosa e della riorganizzazione civile. Catania perse così la sua libertà e venne infeudata al fidato Ansgerio, già abate di S. Eufemia. Questi venne anche nominato abate dell'Abazia benedettina di S. Agata, e vescovo di una diocesi molto larga (da Mascali a Enna e Piazza Armerina). Questa configurazione del potere, con la riunione delle tre cariche - tutte sostenute da pingui rendite - sarà a lungo un elemento determinante nella storia della città. Contemporaneamente, dopo il 1078, si iniziò a costruire la Cattedrale, nello stile di una Chiesa-fortezza, dotata di muraglioni possenti e di torri, vicina alla costa in modo da controllare il porto.
Città feudale, Catania lo rimarrà per quasi centocinquanta anni: il tempo di sviluppare un ceto urbano - mercantile e produttivo - relativamente autonomo. Di questo processo non sappiamo molto; nondovette essere facile, anche perché la città fu distrutta dal terribile terremoto del l169 che infuriò su gran parte della Sicilia orientale; per questa occasione si fa la cifra, esagerata, di diecimila morti, tra i quali lo stesso vescovo Giovanni Aiello, perito con gran moltitudine di persone tra le rovine della Cattedrale ove si officiava la festa della patrona.
Catania doveva aver raggiunto comunque un buon grado di vitalità, perché appena trent'anni dopo il terremoto, in pieno fervore di ricostruzione, la troviamo parteggiare per gli ultimi eredi degli Altavilla e ribelle contro Enrico VI, il figlio del Barbarossa.
La punizione ad opera del furor theutonicus imperiale fu terribile e le cronache parlano di "distruzione" della città; la Cattedrale venne data alle fiamme, con la probabile perdita dell'archivio capitolare e di parte del tesoro.
Anche contro Federico II Catania insorse nel 1232, subendo un secondo devastante saccheggio. A guardia di essa, Federico fece iniziare la costruzione del Castello Ursino, potente pedina in un sistema di fortificazioni che da Messina a Enna a Siracusa serviva a tenere la Sicilia orientale.
Sotto Federico II, però, la città si liberò dalla giurisdizione feudale del vescovo-abate, divenendo città regia (demaniale); e nel 1240, insieme con Castrogiovanni e Piazza Armerina, altri centri importanti della diocesi vescovile, viene riconosciuta come Comune e invitata ad eleggere rappresentanti al Parlamento.