The shipwreck of St. Paul in 60 AD is recorded in some detail in the Acts of the Apostles.  The Apostle Paul was, at this time, being conducted to Rome under arrest to be judged before Caesar as was his right as a Roman Citizen. Amongst the other prisoners was the physician St. Luke who recorded the account of that eventful journey. 

A strong tradition in the Maltese Islands states that St. Paul was shipwrecked in Malta and that St. Paul stayed in Malta for three months and performed a number of miracles. Tradition has it, that St. Paul converted the Maltese to Christianity, but there is no historical evidence to prove it. This is because the earliest archaeological evidence of Christianity in the Maltese Islands are the Christian burial sites known as Catacombs. However, these date to the 4th century A.D.; which is much later than St. Paul's shipwreck in Malta (60 A.D.) as recorded in the Bible.

According to this tradition, the nearest habitation to the place of shipwreck was the villa of Publius, the
protos or governor of the Island. All those who had been shipwrecked spent three days there and after they had regained their strength they moved on to Melite, the main town on island. In the city Paul cured Publius' father of a fever after which the governor of the Island was converted to Christianity and later ordained Bishop by St. Paul. St. Publius was the first bishop of Malta.

After three months, by which time, the sea was again reckoned to be safe for navigation, and loaded with gifts from his Maltese friends, Saint Paul sailed away to Rome and to his subsequent martyrdom.

When the Roman Emperor Constantine embraced Christianity and made it the official religion of the Empire it may be assumed that Christian worship was better organized and that a number of places of assembly were built in various places in the islands.
Tradition has it that one such church was built on the site of the palace of Publius, where St. Paul had cured the father of the governor of the Island.  Many times rebuilt, the site is now occupied by the Cathedral Church dedicated to Saint Paul at Mdina. 

The tradition of St. Paul's shipwreck on the Maltese Islands, although not backed by clear archaeological evidence, is deeply embedded in Maltese culture and every year the Maltese commemorate this event on the 10th of February, which is a public holiday.

The menorah, a symbol discovered at St. Paul's catacombs.  Its presence there suggests that these catacombs were also used by a Jewish community in Malta.