Malta: The Sacred Island.
A title set in history evidenced by some of humanity's earliest free-standing buildings in the shape of the megalithic temples found here. Over 50 sites have been identified, ranging from around 4,100-2,500 B.C., however nothing comparable may be found at nearby Sicily or in any other part of the Mediterranean. 

ARRIVAL OF THE APOSTLE PAUL

According to the Acts of the Apostles, Paul of Tarsus was shipwrecked in Malta while in transit from Caesarea Maritima to Rome, sent by Porcius Festus, procurator of Judea, to stand trial before Emperor Nero. 

(Acts 28:1-11)

According to tradition, during his 3-month stay on the island, Paul converted the Roman Governor Publius, and established him as the first Bishop of Malta. 

Due to the nature of religion and the way it spreads through individuals and societies Christianity could also have been introduced by merchants and other travellers of the time who knew about it or had even converted to this 'new' creed. 

Traditional depiction of the conversion of St. Publius by St. Paul

Tombs, artefacts and inscriptions from the 1st century AD reflect a mixed culture of Punic, Roman and Greek origins. 
Careful observation also reveals the eventual merging of pagan religious traditions and practices with Christian and Orthodox ones.
Various historians including the late Professor Wettinger agree that archaeological evidence spanning from the first eight centuries (AD) indicate an eventual transition to the Orthodox tradition rather than the Roman Catholic version.   

Unusual Paleo-Christian surface tomb with a simple cross at tal-Wey, l/o Mosta, Malta. Simple crosses to denote Christian graves were used between the 1st-4th Centuries AD. 

One must also consider that back in the 1st Century AD, both versions of Christianity originated from the same or related primary sources, and were essentially one religion, with the first differences relating more to symbols and depiction rather than dogmatic divergences. There was also a strong pagan background as mentioned earlier, which is why some key dates and events are replicated on former Roman, hence pagan festivals.
It would be several centuries and ecumenical councils later that would result in a universal set of rules, practices and properly established creed.

The transition of the Roman Saturnalia winter solstice festival to Christmas is a classic example of the pagan background and culture of the time

As the first centuries of the new millennium rolled ahead, the once mighty Roman Empire started to crumble and shrink. 

The establishment of Constantinople in the East as an alternative centre of power would eventually enable a split hence avoiding the irreversible decline and final collapse of the West. 
This separation would be reflected in everything from art to coinage, language and creed, leading to a gradual fading of Latin elements and growing transition to Greek. 
The archaeological record shows that Malta was indeed governed by the Byzantines following the Empire's partition in 395 AD right up to the Arab takeover of around 870 AD. (1)

Byzantine statuette found in Ghajnsielem, Gozo in 1771 with Gnostic symbols of Greek rather than Latin origin

 There remains a heated debate about whether St. Paul did come to Malta and establish Christianity here, and about his connection with Publius, but it is certain that between the 5th-8th Centuries, the established tradition was Orthodox. 
The eventual fall of Rome and growing Byzantine influence is reflected by the introduction of crosses within circles and other Orthodox / Greek symbols such as the Kyros rather than simple crosses to denote Christian graves.
This does not exclude the probability that the Roman tradition did co-exist on a smaller scale as did the Jewish faith beyond the 5th Century AD. 

Notes & References:
(1). Christianity was re-introduced by the Normans who by then practiced the Roman tradition, and reinforced by many of those that came later, especially when the Order of St. John governed the islands.
Images:
1. Conversion of St. Publius by St. Paul - F.S. Said - TOM (30.4.20)
2. Tal-Wey Tomb Collage - Chev. J.P. Cuschieri - It-Tarka (HPM Website - Christian Tombs Page)
3. Les Saturnales Painting by A-F. Calles - Invaluable Auction Catalogue (Lot 140 - 11.2014)
4. Gozitan Statuette - Malta Illustrata Plate XXI (crop) - Count G.A. Ciantar - c.1772