Lilybaeum was an ancient city in western Sicily, with a huge Christian cemetery with catacombs and small hypogei. An ancient tradition without historical confirmation states that the diocese began in the first half of the 2nd century and that its first bishop was a Saint Eustace. According to Praedestinatus, a work by an unknown author in southern Gaul around the mid 5th century, the Gnostic Valentinus' disciple Heracleon began preaching in Sicily, but was firmly opposed by Eustace bishop of Lilybaeum and Theodore bishop of Palermo, who both denounced him to Pope Alexander I. The second traditional bishop was the martyr Gregorius or Gregory, living between the 3rd and 4th centuries but only recorded in the life of the 7th-8th century Saint Gregorius, bishop of Girgenti. The first historically-confirmed Bishop of Lilybaeum was the mathematician and astronomer Pascasinus, captured and taken to Africa by the Vandals. After his return to Sicily he wrote a letter to Pope Leo I in 442–443, mentioning an event in the diocese in 417, meaning it had definitely been founded by that date. Leo I sent Pascasinus a letter via the other Sicilian bishops in 447. Pascasinus later became Leo's legate to the 451Council of Chalcedon, which at the pope's request definitively fixed the date of Easter as the first Sunday after the first full moon of spring. No further bishops of Lilybaeum are known until the 6th century, when the letters of Gregory the Great mention Theodore and Decius. One of these letters mentions that Adeodata, a woman from a patrician family, had founded a nunnery dedicated to the martyr saints Peter, Laurence, Hermes, Pancras, Sebastian and Agnes in her house in Lilybaeum. At that time Sicily was part of the Byzantine Empire and - as emerges in the letters - Sicily's dioceses reported directly to Rome rather than having a metropolitan bishop. Another bishop of the diocese, Elijah, took part in the 649 synod in Rome, whilst Theophanes was one of the church fathers at the Second Council of Nicea in 787. In the meantime, following the, Leo III the Isaurian removed Sicily from Rome's jurisdiction and placed it under the Patriarch of Constantinople around 732. Lilybaeum appeared as one of the suffragan dioceses of the Archdiocese of Syracuse in the Notitia Episcopatuum edited under Leo VI the Wise and dating to the early 10th century., though that situation was theoretical since the island had been conquered by the Arabs in 827 and there was no news from the diocese. When the Normans conquered Sicily in the 11th century the Diocese of Lilybaeum was not reestablished, with its territory instead assigned to a new Diocese of Mazara del Vallo with its seat at Mazara. In 1966 Lilybaeum was made a titular see of the Roman Catholic church, currently held by Giuseppe Leanza, apostolic nuncio to the Czech Republic.
