Ruggero d'Altavilla, nel 1072, vi fece costruire un castello, poiché  l’etnia di Paternò era principalmente d’origine greca. Da qui mosse per la riconquista ed il controllo di città come Catania, che, invece era d’etnia predominante araba. L'Altavilla trasformò Paternò in Contea e la diede al genero Ugo di Jersey. Nei vastissimi territori della contea erano compresi piccoli feudi che coincidevano con conventi e monasteri, soprattutto benedettini. Gli ampi e fertili terreni, ricchi di fonti d’acqua, producevano beni alimentari in grande quantità. Per questo veniva chiamata Civitas Fertilissima,  cioè "città molto fertile".
La contea paternese divenne di Enrico Del Vasto, dopo il matrimonio tra il Conte Ruggero e Adelaide del Vasto, del 1089. Gli succedette il figlio Simone. nel 1137, e, infine, nel 1143, Manfredo, il figlio di quest'ultimo.

A causa del matrimonio tra la principessa normanna Costanza d'Altavilla (figlia di Ruggero II di Sicilia) e l'imperatore Enrico VI, nel 1194, la Sicilia passò sotto la dominazione sveva. Dall’unione nacque, successivamente, il famoso re Federico II. Durante la sua reggenza, Paternò venne amministrata da Beatrice Lanza. Nel 1256, il controllo passò all'aleramico Galvano Lancia.

Lo scontro tra dinastia sveva e i francesi d’Angiò, si ripercosse, non solo sulla Sicilia, ma in particolare su Paternò. Ai Lancia, infatti, fedeli alla dinastia sveva, successe Manfredi II Maletta, il quale, tradendo i tedeschi, aprì la città agli angioini, che la occuparono. Il periodo della dominazione francese, comunque, non durò a lungo. I Vespri siciliani e la lunga guerra che ne derivò, portarono sul trono siciliano gli Aragonesi (1299).

Il possesso della città etnea divenne assai prezioso. Infatti, nel 1302, il sovrano Federico III d'Aragona la donò alla consorte Eleonora d'Angiò, inserendola nella cosiddetta Camera Reginale. Le Regine che seguirono ebberò in eredità Paternò. Dopo un breve periodo, in cui il suo governo fu conteso tra le famiglie nobili degli Alagona, Palizzi e Chiaramonte, passata al Regio Demanio (1396), essa tornò di proprietà della regina Bianca di Navarra, per volere del consorte, il re Martino (nel 1403). Due anni più tardi furono emanate le Consuetudini di Paternò, che contenevano un sistema di norme civili.
Tuttavia, questo periodo di centralità del paese di Paternò durò fino al 1431, quando esso fu venduto da re Alfonso I d'Aragona a Niccolò Speciale e poi, nel 1456, definitivamente, a Guglielmo Raimondo Moncada. Paternò, quindi, divenne un nuovo feudo siciliano. Con esso, nonostante il buongoverno e nonostante la nomina a principato (nel 1565, con decisione di Filippo II di Spagna), Paternò ebbe un lento ma progressivo declino.
Il nuovo rango di principato portò all’inurbamento di famiglie nobili e di ceto borghese, oltre che semplici abitanti. Il centro civico registrò un deciso sviluppo urbanistico. Dopo il terremoto del 1693, Paternò alta, sulla collina, cedette in favore della parte bassa, più sicura, che lentamente si sviluppò nel secolo successivo. Giunsero a Paternò molte confraternite, che edificarono nella parte bassa chiese, conventi ed edifici religiosi, oltre alla presenza di edifici civili e residenze nobiliari.
Nel 1812, con l’emanazione della Costituzione siciliana, furono aboliti  la tortura, il maggiorascato e, soprattutto, i diritti feudali, i Moncada persero la proprietà di Paternò. Venne promulgata anche  l'uguaglianza in campo giuridico.