[2] Según una antigua tradición, no confirmada históricamente, la diócesis existía ya en la primera mitad del siglo II, y su primer obispo sería san Eustaquio.
En el Praedestinatus, obra compuesta por un autor anónimo en la Galia meridional, hacia la mitad del siglo V, se cuenta que Eracleone, discípulo del gnóstico Valentino, empezó a predicar en Sicilia, donde encontró la oposición de los obispos Eustaquio de Lilibea y Teodoro de Palermo, que lo denunciaron ante el papa Alejandro I (105-115).
[3] No se conocen más obispos de Lilibea hasta finales del siglo VI.
[3] La diócesis todavía se menciona hacia los siglos VII y VIII.
[3] Desde el tiempo de Gregorio Magno, la Sicilia hacía parte del imperio bizantino; sin embargo las diócesis sicilians no tenían un metropolitano y dependían todas de Roma.