Beginnings
On 3rd January 1840, during the pontificate of the 254th pope, Gregory XVI (1831-1846), Malacca came under the jurisdiction of Bishop Courvezy, Apostolic Vicar of Siam, of the Paris Foreign Mission (MEP). It is one of the five districts of the MEP Mission of the Malay peninsula and Singapore.

In 1841, Frs JM Beurel and Paul Brigandet were sent to Malacca to open a Mission. They purchased a Dutch house within the old Fort area which became their residence and chapel. Efforts to begin the Mission failed mainly because of hostility and ecclesiastical disagreements from the Portuguese Mission. Without any success, Frs Beurel and Brigandet left Malacca. It must be understood that at this time, the Portuguese Mission (based in Macao) was already well established in Malacca with St Peter's Church as its main parish.

In 1845, Fr JB Boucho, Administrator of the Vicariate of Siam, assigned Frs Peter Favre and John Dastugue to make another attempt to start a new mission in Malacca. The year 1845 marked the 300th anniversary of the first arrival of St Francis Xavier to Malacca on 25th September 1545. The priests found 15 Catholics who were loyal to the Apostolic Vicar of Siam and they became the first parishioners of the new parish of St Francis Xavier, the great Apostle of the Indies and the Missions. The parish was established at the Dutch house purchased earlier.
 

First Register Entries
The first entry made in the parish register was the baptism of an infant, James Louis Ratton, by Fr Favre, the first parish priest on 8th June 1845. The first marriage was a mixed marriage solemnised by Fr Favre between John de Souza and Catherine Neubronne, a Protestant on 21st October 1845 after obtaining a dispensation from Bishop Boucho. The first Asian convert was a 24 year old Chinese man named Peter who was baptised on Christmas eve 1845 in the presence of his Chinese godfather, Anthony. The first burial conducted by Fr Favre was that of Eleiza Gomes on 10th February 1846. The first First Holy Communion and Confirmation were administered by Bishop Boucho on 31st May 1846. By the end of 1845, the parish had 200 members.

Mission to the Aborigines
In 1848, a mission for the aborigines was established at Rumbia named Dusun Maria (Mary's Village) and Fr Peter Borie was in charge of the pastoral care of the Mantra (Orang Asli) tribes. In 1860, the land reverted to the government and a replacement land was given at present day Ayer Salak and was named Maria Pindah. A church, presbytery and two schools were completed by 1864. The work among the Mantras took a heavy toll on the missionaries and three priests died of malaria. The remains of two of them who died in Malacca, Frs Thomas Bourlier (died 2nd April 1855) dan Charles Desbons (died 11th May 1876) were interred in the crypt of the Church of St Francis Xavier.
 

Church Building began
The Resident Councillor of the East India Company in Malacca, in a reply dated 16th April 1849 to Bishop Boucho, made an offer to sell a parcel of land for the expressed condition of buildings of religious and educational purposes. The offer was the site of the ruins of the Dominican Convent of Our Lady of the Rosary and the ramparts of the A Famosa near the Bastion of St Domingo.

The offer was accepted and Fr Favre began the work of building a new church based on a neo-gothic design, believed to be based on the model of the Cathedral of St Peter in Montepellier, southern France. Fr Peter Barbe was posted to Malacca to assist him in 1849. Fr Favre was sent by Bishop Boucho to Mauritius and Bourbon Islands to raise funds for the new church as the progress of the work already begun was dependant on sufficient funds and available building materials. Fr Barbe was left alone to continue the work until the arrival of Fr Marie Jean Francois Allard in 1850. They struggled to build the church relying on funds trickling in from Fr Favre. In 1850, Fr Favre went to Brazil, Peru, Chile and Argentina on his fundraising campaign.

In October 1854, Fr Favre left Malacca and returned to France for health reasons. Fr Barbe also left Malacca to take up another posting thus leaving Fr Allard with daunting task of completing the building of the church. Fr Peter Paris arrived in 1856 to assist him until 1858.
 

Completion of building
Finally in 1856, the church was completed for general use and Bishop Boucho blessed the new church on 13th January 1856. The church towered over other buildings in the vicinity and dominated the skyline of Malacca. For a very long time, the church of St Francis Xavier was the largest built by the MEP in the Malay peninsula.

In one his despatches to Fr Albrand, superior of the Paris Seminary dated 22nd February 1856, Bishop Boucho wrote, "The fine church of Malacca on the point of being completed, my presence to bless it had been requested. So I left for Singapore on the feast of the Holy Innocents and from there went to Malacca, in the company of Fr Beurel, who was also invited to this solemn occasion. But when we arrived there, we found that the building was not yet ready to be blessed. They had to postpone to the following Sunday this blessing we expected to do on the feast of the Epiphany.
Fr Beurel who could not be absent for so long because urgent business, returned to Singapore after the Epiphany. So it was on 13th January that I had the pleasure to bless this beautiful building which is the glory of Catholicism, not only in the Straits but even, according to the best experts in the art of building, in the whole of India. For me, its only flaw is that it is in Malacca and not in Penang. The ceremony took place with all the pomp we could display. The Mantras in great number were in one wing and the Chinese in the other, whereas the main nave was filled by the hat people. There were no less than 500 people."

The finishing touches to the church were completed in 1859 by Fr Allard. In 1874, the present day presbytery was built.