Palermo blev grundlagt af fønikerne, ca. 800 år f.Kr., ved bredden af havet. Af denne første by er der i dag intet tilbage ud over byplanen, som har været kopieret igennem århundreder: en lang gade, der fra havet går til den lave bakke, hvor regeringsbygningen stadig ligger.

Den var base for kartaginienserne og senere for romerne. Også fra romersk tidsalder er der kun få spor tilbage, selv om det var et blomstrende bystyre. Byen lå langt fra imperiets centrum og endnu længere væk i forhold til Konstantinopolis, da Sicilien blev en lille del af det Østromerske Rige.

I 831 faldt Palermo efter ét års belejring i arabiske hænder. Dette blev begyndelsen til et nyt liv for byen, der i løbet af få år voksede op til en storby og på grund af sin pragt at sammenligne med Cordova og Kairo. Palæer, moskéer og storslåede parker blev grundlagt i denne “Vestens Medina” med slanke minareter, der stod mod horisonten. Byen, som blev kaldt Balarm, var hovedstad i det sicilianske emirat og siges at have haft 300.000 indbyggere.

I 1061 startede Robert Guiscard med sin normanniske hær erobringen af Sicilien, og elleve år efter nåede han til Palermo. De nye herskeres komme betød dog ikke den arabiske kulturs forfald, tværtimod. Skønt normannerne på den ene side demolerede moskéerne, så brugte de på den anden de arabiske arkitekter til bygningen af deres herlige palermitanske palæer. Selv om de tog herredømmet over hele Sicilien, så overlod de dog administrationen til de dygtige islamiske embedsmænd. Under Roger II., den første sicilianske konge,nåede Palermo sit højdepunkt, som hovedstad i det normanniske rige. Byen var centrum for en livlig handel mellem Orienten og Occidenten, og fra alle lande strømmede adelige, handelsmænd og eventyrere til denne rige stad og til det strålende hof. Palæer og kirker i arabisk-normannisk stil blev bygget og er den dag i dag de vigtigste attraktioner i Palermo.

Denne storhedstid fortsatte under Frederik den Anden af Schwabien, der gjorde Palermo til datidens største kulturcenter. Aldrig senere nåede Palermo en lignende glansperiode, selv om den under det spanske herredømme blev beriget af adskillige barokke bygninger.

Et glimt af fortidens storhed kom tilbage til byen i begyndelsen af det 20. århundrede, da Palermo levede sin Belle Epoque takket være en gruppe forretningsmænd, som bragte et pust af modernitet, og som ud over det økonomiske også hævede det kulturelle og kunstneriske niveau.

Fra 1946 er Palermo hovedstad i den autonome region, Sicilien. Det er en moderne by med ca. 730.000 indbyggere og rig på monumenter fra alle tidsaldre.