Polizzi fu detta “Baseapolis”, città del re, dai Bizantini che vi costruirono notevoli fortificazioni, soprattutto sulla rocca. Questi furono assoggettati dai Saraceni nel 882: si racconta che in questa occasione tremila teste di cristiani furono inviate a Palermo quale "trofeo di guerra".

I bizantini superstiti si stabilirono in contrada S. Pietro e nel quartiere della Chiesa di San Pancrazio. I Saraceni, espugnata la Rocca, estesero i loro domini al borgo di Rahalburd (Scannali) e fondarono una moschea che nel 1361 diventerà la Chiesa di Sant'Antonio Abate.

Nel 1071 Polizzi fu liberata dai Normanni. Ruggero, dopo aver fortificato il maniero sulla Rocca, vi costruì un nuovo Castello (il cosiddetto "Castellazzo") in contrada Campo (oggi delle due fortezze rimangono solo ruderi): si racconta che fosse un dono di nozze alla figlia Matilde, sposa di Ranulfo Maniace. Nel 1082, la nipote del sovrano normanno, la contessa Adelasia, sposa di Rinaldo dell'Aquila, ampliò notevolmente l'abitato, concedendo asilo a diverse etnie.

Nel 1234, Federico II di Svevia, diede alla città il titolo di "Generosa". Nel 1282 Polizzi prese parte ai Vespri Siciliani contro la dominazione aragonese. Nel 1398 divenne una delle 42 città demaniali.

Nel 1352 i Ventimiglia riuscirono a toglierla ai Chiaromonte, ottenendone pieno controllo nel 1354. Nel 1393, Polizzi si dichiarò "città vassalla" del re Martino Il Giovane ma, per sostenere le guerre della Corona, si indebitò e finì nelle mani del feudatario Raimondo Caprera. Solo nel 1443 Alfonso D'Aragona riscattò la città e la restituì al demanio rendendola "intoccabile". Durante il Rinascimento, Polizzi attraversò un periodo di splendore turbato dalla grande siccità del 1547-1548 e dalla pestilenza del 1575 che falcidiò la popolazione.