Construction of the church began in 1853 as the population of the small village of Sliema began to grow. The inhabitants of the small hamlet had petitioned the religious authorities for the construction of a larger church to suit their spiritual needs. Permission was granted on condition that the new church was to be dedicated to St. Paul the Apostle. For this purpose the diocese of Malta also donated the land on which the new church was to be built on. However the villagers had a very strong devotion towards Our Lady and wished their main church to be dedicated in honour of their Patroness. The name of the village itself has a very strong connection to Our Lady. Indeed, Sliema got its name from a 16th-century chapel that stood on the Tigné promontory dedicated to The Virgin Mary, which served as a beacon and a reference point to the few fishermen who lived in that area. The name could thus be connected with the first words of the Hail Mary prayer, which in Maltese is "Sliem Għalik Marija". Sliem is the Maltese word meaning peace. The villagers had it their way and on 29 April 1853 the foundation stone of the new church dedicated to Our Lady Stella Maris was laid. Two years later the construction work was finished and on 11 August 1855 the church was opened for public worship. A week later the first titular feast was celebrated both inside the church and externally, marking the birth of the Sliema community.
Parish Church
The population of Sliema continued to increase rapidly and soon the church built in 1855 had to be enlarged. By 1877 these works had been finished and the church reached its current size crowned with a majestic dome. These works had been finished in time for a petition collected among the inhabitants of Sliema asking for their church to be erected to the rank of Parish Church. On Christmas Day of 1878 the much awaited wish was granted and Sliema had a Parish church of its own. Previously it fell under the jurisdiction of the Parish of St. Helen's in Birkikara. The church was embellished with various works of art throughout the years, most notably the apse painting by Giuseppe Calì and the Titular statue of Our Lady Stella Maris that was brought to Sliema from Paris in 1891. This statue is carried annually in procession throughout the streets of Sliema on the 3rd Sunday of August when the Titular Feast is celebrated with great pomp. The church suffered severe damages during World War II on 2 March 1942 during a German air raid. Besides structural damages various works of art had been lost. Through the efforts of the parishioners repairs started immediately, and by December of that same year, the church was partially opened again. The first Parish priest was Fr. Vincenzo Manche while the current one is Mgr. Anton Portelli who is now the first archpriest after archbishop Charles Scicluna raised the parish to the dignity of an arch parish through a decree dated 8 May 2018.
