Diversi sono gli storici che hanno scritto su Polizzi, e diverse le ipotesi avanzate sulle sue origini. Alcuni la identificano con l'Atene siciliana, di cui parla Diodoro Siculo, altri sostengono che sia stata fondata dai bizantini, altri ancora che tragga origini dall'antica Palica.
Per avvalorare quest'ultima ipotesi gli storici accennano anche ad un fonte, che ancora oggi si può ammirare ai piedi del colle su cui sorge la cittadina, detto Naftolia forse da Naftalia, cioè fonte di Thalia, madre dei Palici.
Di certo, e questo lo confermano i numerosi reperti archeologici del IV e III secolo a.C. che sono stati ritrovati nel corso degli anni, Polizzi è stata abitata fin dalle antichità.
Di tutti questi reperti archeologici bisogna ricordare la statua triforme di Iside ritrovata nel XVII secolo in un pozzo e collocata nella chiesa Madre fino al 1764, quando fu rimossa per dei lavori. Nel 1771, alla fine dei lavori di ristrutturazione della chiesa Madre, la statua doveva essere ricollocata al posto originale, invece venne distrutta per volere dell'allora vescovo di Cefalù, mons. Castelli, perché iteneva la presenza di una statua pagana all'interno di una chiesa una profanazione. Altri reperti, ritrovati nel corso delle diverse campagne di scavo che si sono susseguite in questi ultimi decenni nella necropoli ellenistica di contrada San Pietro, si possono ammirare nel locale museo archeologico.
Il nucleo attuale, molto probabilmente, si è sviluppato durante la dominazione bizantina.
I Bizantini, infatti, per contrastare l'avanzata degli Arabi nel Val Demone, impiantarono una base strategica proprio sulla rocca dove sorge l'odierna Polizzi dandole il nome di Basileapolis, cioè Città del Re, divenuto in seguito, molto più semplicemente, Polis, e in Arabo Bulis.
Nell'882 i Saraceni, nei pressi di Polizzi, inflissero una dura sconfitta ai Bizantini. A seguito della battaglia tremila teste di soldati cristiani vennero inviati a Palermo come trofeo di guerra.
Dopo la conquista degli Arabi, i Greci di rito Bizantino si stabilirono attorno alla chiesa di San Pancrazio e nel borgo in contrada San Pietro. Gli Arabi, invece, fissarono la proprio dimora oltre che sulla Rocca, nel borgo di Rahalburd (Scannali); mentre i cristiani di rito Latino furono presenti, sia prima che dopo la conquista Araba, attorno al Monastero di Santa Maria de Heremitis o de Gadera.
Con l'arrivo dei Normanni in Sicilia, e la conquista delle Madonie verso la fine del 1071, Polizzi si sviluppò notevolmente. Il gran conte Ruggero, infatti, ne fece rafforzare il castello esistente e ne costruì uno nuovo (1074) in contrada Campo, per meglio controllare i due versanti dell'Imera Settentrionale e Meridionale e la principale via d'accesso verso l'interno dell'isola.
Nel 1082 il conte Ruggero donò il castello di Polizzi ed il suo territorio alla nipote Adelasia. La contessa Adelasia, moglie di Rinaldo dell'Aquila, diede notevole impulso alla crescita di Polizzi che divenne, così, uno degli insediamenti fortificati più importanti dell'area madonita.
Nel 1234 l'imperatore Federico II attribuì a Polizzi, in quanto città demaniale, il titolo di "Generosa", titolo che conserva come parte integrante del suo toponimo. Le città demaniali furono 42 e Polizzi occupò il 21° posto. Il centro ebbe, inoltre, un proprio blasone costituito da un campo celeste con sette rose.
Nel 1282 la città partecipò ai Vespri Siciliani, contribuendo con truppe e viveri, per cacciare gli Angioini e favorire l'arrivo degli Aragonesi.