Pur avendo una linga storia, che inizia con le città del periodo siculo, Hybla Major ed Imessa, il suo toponimo ha origini più recenti. Come periodo d’origine vari studiosi lo pongono in età bizantina. Il linguista Giovanni Alessio sostiene che l’origine del nome di Paternò derivi dal paese vicino di Adernò (nato anch’esso in periodo bizantino). In particolare, Il toponimo deriverebbe dal termine greco ep-Adernòn, traducibile come “verso Adernò”.

Lo storico Gaetano Savasta, invece, nel suo libro Memorie storiche della città di Paternò (del1905), fa nascere il toponimo del paese etneo dal latino, invece che dal greco. Esso deriverebbe da Paetram Aitnaion, cioè, “Rocca degli Etnei”. Il termine Aitna è l’antico nome del villaggio di Imessa. Egli conferma l’ipotesi formulata dallo studioso Leandro Alberti, che, nel XVI secolo, poneva la nascita di Paternò in periodo romano.

Altra teoria, simile a quest’ultima, risale al geografo arabo Al-Muqaddasi, che, nella sua descrizione della Sicilia, chiamava il paese etneo come Batarnù (molto simile a ep-Adernòn), sostenendo, tra l’altro, che il toponimo risalisse ad epoca precedente a quella araba.
Al di là delle possibili origini, sappiamo che, sotto la dominazione normanna, il paese assunse il toponimo di Paternionis.

La leggenda
Sull’origine del toponimo esiste a Paternò anche un’antica leggenda. Si narra che due soldati romani stavano violentando una donna del posto. A difesa della ragazza accorsero un vecchio e un giovane (suo figlio). Uno dei due fu ucciso, mentre l’altro riuscì a scappare anche se ferito. I due locali, catturati, furono sottoposti a giudizio. Il militare ferito, però, riconobbe solo il giovane. Questo interrogato alla domanda di chi fosse l’anziano non confessò l’identità del padre. Il giovane fu giustiziato.
Si narra che il vecchio non morì mai, divenendo parte del paesaggio stesso. Da allora il paese fu denominato, per l'appunto,  “Pater-nò”.