Le diocèse est érigé au Ier siècle. Selon la tradition, le premier évêque est envoyé par saint Pierre. La première mention historique du siège de Palerme est dans une lettre du pape Léon Ier, datée de 442 ou 443 et adressée à l'évêque Pascasino du diocèse de Lilibeo(it). Lors de l'occupation arabe, il n'y a pas d'évêques de Palerme ; Au milieu du XIe siècle, Palerme est élevée au rang d'archidiocèse métropolitain. En 1049, le pape nomme Humbert de Moyenmoutier comme archevêque mais les Normands ne l'autorisent pas à débarquer en Sicile. La succession épiscopale ne reprend qu'en 1065 avec l'archevêque Nicodème. En 1176, l'archidiocèse cède son territoire de Corleone à l'archidiocèse de Monreale.
Le , à la demande de Ferdinand III de Sicile, le pape Pie VI unit aeque principaliter l'archidiocèse de Palerme avec celui de Monreale par le bref apostoliqueApostolici suscepti. Cette union prend fin le quand le pape Pie VII, par la bulle Imbecillitas humanae mentis, replace Monreale comme siège métropolitain indépendant. Le , les paroisses byzantines sont cédées au profit de l'éparchie de Piana degli Albanesi.