Founding and early years

The apostolic prefecture of North Borneo and Labuan was established 27 August 1855. Subsequent to this, the area came under British control, and English-speaking missionaries were sought, and on 19 March 1881, the Vatican assigned evangelization work to the Saint Joseph's Missionary Society of Mill Hill of England. One of the first places the "Mill Hill Fathers" came to was Sandakan. Msgr. Thomas Jackson, the 2nd Prefect Apostolate of North Borneo, arrived in May 1882 to attend a dinner to celebrate the granting of the Charter to the North Borneo Chartered Company in November 1881. In this first visit, he was able to find a suitable spot where the future mission station would be built. He found out that there were about 4,500 Chinese in Sandakan, and thought of establishing a mission for them.

St. Mary's Church before WWII

Subsequently, in May 1883 Msgr. Thomas Jackson bought five (5) acres of land on a hill in Sandakan, and the same year ordered Rev. Fr. Alexander Prenger to establish a mission here. Together they built a temporary hut made of kajang (woven Pandanus), which Prenger dedicated to the Blessed Virgin Mary, and the whole plot named St. Mary's Hill. Having high hopes for the Sandakan Mission, Jackson also asked Rev. Fr. Benedict Pundleider to join Prenger in Sandakan. On 24 July 1883, Fr. Prenger and Fr. Pundleider opened St. Mary's School, the first school in North Borneo. By October in the same year, there was a proper house, a hostel for boys to stay in, and a small church.

St. Mary's Convent, British North Borneo

Sandakan was subject to frequent pirate raids, however, leading many of the people to flee into the interior for safety. Fr. Pundleider thought two priests serving in Sandakan were too many given conditions, and left in February 1884 to open a mission station in Bundu, Kuala Penyu. Left to himself, Prenger tried to consolidate the mission and the school. However, in November 1885, Jackson ordered him to depart, because “Sandakan unhealthy; a wind blowing across the bay; many Chinese sick, no good water in town; and Fr. Prenger often ill.” Fr. Prenger closed the mission and school and opened a mission station in Penampang.

Reestablishment

In July 1886, Rev. Fr. John Byron visited Sandakan and found 26 Catholics. After having been closed for two years, the Sandakan Mission was re-opened by Fr. Byron in May 1887. On 15 August 1887, St. Mary's School was also re-opened. From this year onwards St. Mary's School progressed gradually, with assistant rectors only lasting for a few years. First, Fr. Bernard Kurz joined Fr. Byron in September 1887. He was replaced by Fr. Francis Dibona in March 1888, then Fr. Julius Verbrugge, Fr. John Rientjies in November 1889, and Fr. Albert Reyffert four years later in November 1893.

St. Mary's Convent

In 1891, a school was started for girls. The White Sisters (the Franciscan Missionaries of St. Joseph) opened St. Mary's Convent on 5 November 1891. The first four sisters were Sr. Theresa, Sr. Peter, Sr. Rose and Sr. Collete. This was the first convent to be opened in North Borneo. After the year 1899, Sandakan was an established Mission with a presbytery, a boys’ school, a convent, and church. Rev. Fr. Cornelius Keet became the rector. In the same year, a great number of Catholic Filipino refugees fled to Sandakan because of the war in the Philippines. This created an artificial increase in the Catholic population. In 1900, Rev. Fr. Cornelius de Vette came to assist. The year 1903 saw the arrival of more Filipino refugees. In 1904, de Vette built a permanent church in Sandakan. The next several years in the history of the Mission and School in Sandakan followed much the same pattern of short tenureship of various priests.

Towards the end of 1907, the situation became normal in the Philippines, and many Filipinos returned home. Between the years 1909 and 1920, a number of Mill Hill Fathers came to keep the mission going, but some stayed only for a year and others for two years. Within this period, Tawau was opened as an outstation mission of Sandakan in 1915. With the frequent transferring of the Fathers in and out of Sandakan, there was no continuity in mission work, which could not be expected to improve much. Furthermore, some of the Fathers spent more time in the school.

St. Mary's Cathedral(Interior)

In early 1920, with the appointment of Rev. Fr. Aloysius Stotter as rector in Sandakan, mission work became more active. The school also improved day by day. He built a three-storey building, and with Rev. Fr. Bernard J. Davis running it, became the best school in North Borneo. In 1923, Fr. Stotter wanted to devote most of his time taking care of the growing number of Catholics. He contacted the La Salle Brothers to take over the school, but no agreement could be reached. The Fathers who came later continued the work of expansion by the previous Fathers.

The next couple of decades seem to be clouded in “history” as few records are available. The Mission continued to progress until the Second World War when the European priests were arrested and sent to war camps. According to Rev. Fr. Laurence M. Parsons, “I arrived to Sandakan in November 1933 to take charge of the Mission. I was lent to Jesselton for a year in 1935, and then went back to Sandakan until I was taken away by the Japanese. The Japs razed St. Mary’s to the ground in 1943.”

Postwar revival

When Parsons returned to Sandakan in November 1946, there was neither church nor school standing, except for the pillars and the concrete part of the wall of the boys’ school. An attap roof was put over these pillars and concrete walls, and the school re-opened in 1947. The reconstructed structure doubled as a church and school. Fr. Davis continued to be the principal of the school.

Father Mulders Centre

The period after the Second World War belongs, however, to Rev. Fr. Anthony Mulders, who oversaw the difficult process of reconstruction after the devastation of the War. Mulders arrived in Sandakan in 1952, and wasted no time in rebuilding both the primary and secondary school buildings. He then began to bulldoze the hill to level a site for a permanent church. This led to serious erosion, but after that problem was solved, St. Mary's Church was finally constructed, opened, and solemnly consecrated in 1961 by the Rt. Rev. Bishop James Buis, the Vicar Apostolic of Jesselton. Fr. Mulders transformed the mission compound beyond recognition, making it one of the finest sites in Sandakan. A rectory was built in 1967 for the priests, who had been staying in the schools. The next development was the building of St. Joseph's Church, supervised by Rev. Fr. Francis van den Schoor. It was completed and blessed in 1971.

As the schools and church flourished, six to seven priests were sent to Sandakan to teach in the schools and to minister to the parishioners. This has resulted in a fast growth rate in conversion. However, hard times came in the 1970s as a new immigration policy required most of the foreign priests to depart from Sabah, leaving Sandakan with only one priest. Eventually, Fr. van den Schoor the parish priest was also ordered to leave.

In April 1972, Rev. Fr. Thomas Sham became the parish priest. Apart from carrying out his priestly duties, he set up the Catholic Women's League and the Parish Council. He also built a fence around the church compound, put up a Shrine to Our Lady, and built a parish hall behind the church (present-day Catechetical Room).

Spiritual renewal

Rev. Fr. John Lee, later Archbishop of Kota Kinabalu, replaced Fr. Sham as parish priest in January 1978. At this time, the winds of renewal reached Sandakan. Firstly, it was the Aggiornamento followed by the Catholic charismatic renewal nivenebt. Fr. John Lee encouraged the formation of a Prayer Group in 1979. On 3 October 1978, Sandakan witnessed the ordination of Rev. Fr. Nicholas Ong at St. Mary's Church.

St. Mary's Parish Hall

When Rev. Fr. Aloysius Tung took over from Fr. John Lee in July 1980, he continued to encourage spiritual renewal in the parish. This resulted in the growth of the prayer group and the formation of the first Neo-Catechumenal Community and the Star of Yahweh Covenant Community (SYCC). Renewal seminars continued to be held in 1981 – 1983 which saw a significant increase in the number of spiritually renewed parishioners, and the Church became a hive of activities. The old parish hall became inadequate and Fr. Tung requested the Parish Council to design and build a larger Parish Hall to cater for meetings, seminars and other activities of the parishioners. The new hall, christened St. Mary's Parish Centre, was completed and blessed by Msgr. John Lee on 3 May 1987 just as he received news from Rome of his appointment as the next bishop of Kota Kinabalu.

Rev. Fr. Tobias Chi became parish priest in October 1984, later joined by Rev. Fr. John Mansul, Rev. Fr. Bruno Yasun and Rev. Fr. Thomas Yip, and parish growth accelerated. He organized evangelization talks to gather new  converts and started the RCIA (Rite of Christian Initiation of Adults) in 1985. The evangelization talks were replaced by the Good Tidings Concert and the printing of the Good Tidings Magazine in 1987. These became avenues to evangelize invited guests and also to serve as a platform for the many church groups and communities to work together in unity.

To revitalize and make the Parish Council more representative, Fr. Chi called the first Annual Delegates Assembly in 1986. The delegates were nominated from all the groups and communities and any other parishioners. They met annually to report and deliberate the affairs of the parish, and elected the office bearers of the Parish Council every two years.

One of the most important liturgical events in the parish was the introduction of the Chinese-language Mass, which resulted in the growth of the Chinese Catholic Community. As the various groups and communities grew, it became necessary to form three language coordinating bodies to facilitate communication. This led to the formation of the English Coordinating Committee, the BM Coordinating Committee, and the Chinese Coordinating Committee.

Fr. Chi also initiated the Sunday School programme where children received their faith formation and preparation for their First Communion and Confirmation. In order to further build up the faith of the children and to make the Liturgy of the Word more meaningful and interesting to them, he launched a liturgical team for the Children's Liturgy of the Word, and the first demonstration was done in November 1992.

Under the leadership and encouragement of Fr. Chi, several more projects were completed. A grotto, resembling the grotto in Lourdes, was cut out of the hillside in front of the Church in 1987. It has now been enhanced with a waterfall. The former Shrine of Our Lady was converted to a shrine at St. Joseph's Church. A block of three storey building was constructed for the St. Mary's Kindergarten in 1990. St. Mark's Church and St. Joseph's Multi Purpose Hall were completed and blessed in 1993. In 1995, a new church named St. Paul's was opened in Ulu Dusun. He also blessed the new Sibuga Cemetery and opened it for use. St. Joseph's Church was renovated and beautified in preparation for its Silver Jubilee in 1996. In 1998, both St. Mary's Bandar (boys' school) and St. Mary's Convent were relocated to new school buildings at Mile 2 North Road.

Paitan Mission

The Paitan Mission is an important outreach programme of the parish. It was first initiated by the Light of Jesus Christ Covenant Community, a fraternity laypersons' ministry which was based in Sacred Heart Cathedral, Kota Kinabalu. Later, the cathedral's own fraternity laypersons' ministry known as the Star of Yahweh Covenant Community took over some of the responsibilities. When Rev. Fr. Thomas Yip was posted to Sandakan, he took a personal interest in this Mission and developed it. When he left, Sr. Clarice Jomitin was granted permission to stay and look after the Mission. However, due to conflicting land claims, it was relocated with the generous time and effort of the parishioners. A new mission centre was built and run by Sr. Dorothy Laudi and Sr. Hilary Laudi. They set up kindergartens in the many villages accessible only by boats. Currently this Mission is looked after by Rev. Fr. Thomas Makajil assisted by Henry Wong and other volunteers.

The Diocesan Pastoral Organization Planning Committee (DOPP) was formed in 1995 to study and compile the problems of the local churches for submission to the then-Diocese of Kota Kinabalu for further deliberation and planning. A Diocesan Pastoral Plan was drawn and given to all parishes to adopt. Workshops were conducted in 1997 and 1998 to study the plan before it could be practically understood and implemented.

On 21 January 1999, St. Mary's celebrated the ordination of Deacon John Wong to the priesthood, the fourth local priest after Simon Fung, Michael Mewo, and Nicholas Ong. In 2010, Rev. Fr. John Wong was appointed Coadjutor Archbishop of the Archdiocese of Kota Kinabalu by Pope Benedict XVI.

Rev. Fr. Francis Tsen took over as parish priest in November 1999. He continued the work of renewing the parish. He invited Rev. Fr. Vincent Lee, a Jesuit from Singapore, to give spiritual formation and anointing to the parishioners at a Lenten/Intercessory Retreat in 2000 and a Holy Spirit Seminar in 2001. Fr. Tsen particularly emphasized on the importance of adoring the Blessed Sacrament and intercessory prayers, and had the Blessed Sacrament Chapel built for adoration and intercession. He also showed great interest in the healing and deliverance ministry, and sent some parishioners to Kota Kinabalu to attend seminars. He organized a number of Masses for the healing of the sick in the parish. He started several Bible Sharing and Study groups. He renovated the old Boys’ School for Sunday School use and other spiritual activities. It is now named as the Father Mulder's Catechetical  Centre.

Fr. Tsen went on a long leave in September 2004 and in his absence, Rev. Fr. Saimon William, a local priest who hailed from the Parish of St. Patrick in Membakut, Beaufort was appointed acting parish priest until the arrival of Rev. Fr. Simon Kontou from Penampang in December 2004. After Rev. Fr. Paul Lo's ordination, he was assigned by the then-Bishop John Lee to Sandakan as the second assistant priest. For the first time in many years Sandakan was blessed with three priests. However, this number was reduced to two again when Fr. Saimon was transferred to Lahad Datu in October 2006.

During his tenure in Sandakan, Fr. Saimon had done a lot to beautify the church compound. He initiated the recycling programme and asked the parishioners to donate recyclable items to the church to collect funds for his beautification projects. With the funds, he had a waterfall constructed near the Grotto. Many flowers and trees were planted, and grounds of the church were beautifully landscaped.

Elevation

The prospect of Sandakan being erected to a diocese on the East Coast began circulating at the end of 2005. This probability was more or less confirmed with the visit by the Apostolic Delegate in Malaysia, Archbishop Salvatore Pennachio, to the three main parishes on the East Coast. On 16 July 2007, it was officially announced that Pope Benedict XVI had appointed Rev. Fr. Julius Dusin Gitom as the first bishop of the Diocese of Sandakan, a suffragan of the Metropolitan See of Kuching, thus becoming the third diocese in Sabah after Kota Kinabalu and Keningau. The new diocese covers the entire East Coast of Sabah which comprises the parishes of St. Martin in Telupid, St. Dominic in Lahad Datu, Holy Trinity in Tawau, and St. Mary in Sandakan. With the elevation of the Diocese of Kota Kinabalu to an archdiocese in 2008, the Diocese of Sandakan is now a suffragan of the Metropolitan See of Kota Kinabalu.

Diocese of Sandakan

With the erection of the Diocese of Sandakan on 15 October 2007, St. Mary's Church was elevated to St. Mary's Cathedral. Fr. Simon continued his priestly duties at the cathedral as rector until his transfer to St. Dominic's Church in Lahad Datu in July 2008. He was replaced by Fr. Thomas Makajil. Fr. Thomas was previously assisted by Fr. Paul Lo and Fr. Anthony Muji, and since February 2012 is presently assisted by Rev. Fr. Anthony Mikat. Fr. Thomas began renovation works on the cathedral building in 2010.

St. Mary's Cathedral saw the addition of a covered wing section on the right side of the church in 2011. The construction of a new covered wing section on the left side has just been completed in September 2012. The cathedral can now seat approximately 1,500 parishioners. Two LCD projectors were installed in 2011 to facilitate the parishioners in the viewing of hymns, liturgical prayers and responses particularly that of the New Roman Missal, as well as witnessing the Rite of Baptism and other activities. An LCD projector has also been also installed on each side of the covered wing sections of the cathedral.

Sandakan Diocese was blessed with their first priest, Rev. Fr. David Garaman, who was ordained by the Rt. Rev. Bishop Julius Dusin Gitom in Lahad Datu on 31 December 2010. He had his pastoral immersion at the cathedral as a deacon since 19 March 2010. Two seminarians, namely Marthin Steven and Stanley William, also did their pastoral immersion here as 1st year theology student in 2011 and 2nd year philosophy student in 2012 respectively.

On 24 May 2010, the Good Shepherd Sisters (RGS) established their mission in the Sandakan Diocese by setting up Seri Murni Crisis Centre. The centre offers a safe haven and temporary shelter for about ten (10) women and girls in crisis situations.

In the diocese's fifth year, the Diocesan Pastoral and Worship Centre has been built on the former site of the old Boys’ School classroom block, and was to be blessed on 26 October 2012.