The Parish was set up in 1874. Its boundaries covered the area that embraced the entire Port au Port Peninsula to Mattis Point. Early records indicate that Msgr. Thomas Sears looked after the area and later Father Joseph Veronneau came around 1876. He was later followed by Father McInnis. Father M. O'Rourke served the parish for roughly twenty years until 1899. As time went on new parishes were built. The first was the Parish of Port au Port. In 1937 the Parish of Stephenville Crossing was created.

Stephen Gallant was the first of the Acadian immigrants to be born in Stephenville and was brought to Margaree, Nova Scotia to be baptized. The first record of a baptism for St. Stephen's Parish belongs to Samuel Hynes, son of W. Hynes and Caroline Marche baptized on October 2, 1874. It was Father P. W. Brown who succeeded Dean M. O'Rourke who built the first school at Mattis Point around the turn of the century. His successor was Msgr. P. F. Adams came to Newfoundland from the Gaspe Peninsula in Quebec and served as parish priest from 1906 until 1937. It was during his time that the church was built, around 1909. It was destroyed by fire on October 19, 1969.

Msgr. Adams was instrumental in starting St. Anne’s Guild in 1907. Msgr. Adams was also instrumental in getting the Presentation Sisters to come to Stephenville to administer the schools. The sisters arrived on November 21, 1925, and lived at St. Theresa's Convent. Sister Agnes O'Keefe was the first superior. Upon his death, Msgr. Adams requested to be buried in Stephenville and rests in the West St. Cemetery. In 1937, after Msgr. Adams death, Father Leo Drake was an administrator for one year. Father, later Msgr. Walter Brennan was named parish priest in 1938 and remained at Stephenville until 1951.

Father, later Msgr. Patrick Bromley was a Parish Priest from 1951 until his retirement in 1976. It was during the tenure of Msgr. Patrick Bromley that St. Stephen's celebrated the 100th anniversary of its founding. Following him in 1976 was Msgr. Gerald Hull who was Pastor until his death in January 1984. Father Bernard Buckle was the Parish Priest from 1984 to 1994. Father Edwin Gale was the Parish Priest from 1994 to 2000. Father Maurice O'Quinn was a Parish Priest from 2000 until 2013. Msgr. Jim Robertson was Pastor from 2013 until 2017. Father Poulose Kannampilly served as Associate Pastor from 2014 until 2016. On June 1, 2016, Father Chris Mekala (Krishnarao) became Associate Pastor until June 27, 2017. On June 28, 2017, Father Chris was assigned Administrator of the Parish. Father Vitus Echedo was appointed Associate on June 28, 2017.

Father Vitus returned to Nigeria and Father Andrew H. White was appointed Associate Priest on January 1, 2019. In November of 2020, Father White moved to Codroy Valley St. Anne's Parish to serve as Parish Priest. Father Vanathuraj Rayappan (Ray) came to St. Stephen's Parish and serving as Associate Priest. In December 2021, Father Vanathuraj Rayappan accepted the position of Parish Priest of St. Anne Tshukuminuin Natuashish. May 2022 Fr. Joseph Kizhakkekuruvithadathil, from India, arrived as associate pastor and in the fall of that same year transferred to Lourdes as Parish Priest.

In the fall of 2022, Father Chris left to assume pastoral work in Wisconsin. Father Gerard Patry became administrator on a temporary basis until 2024 when he returned to Pasadena, NL. Fr. Joseph Loko, from Africa, arrived in September 2023 as associate pastor. February 2024, Fr. Loko transferred to Lourdes as Parish Priest and Father Joseph Kizhakkekuruvithadathil returned to St. Stephen’s as Parish Priest. Father Jaison Vizhukipara, from India, joined Fr. Joseph K. as associate pastor. Father Jaison stayed until the fall when he was transferred to another parish in Port au Choix. In March 2025, Fr. Joselet “George” Attuchalil, from India, arrived as associate pastor.

During these last 20 years, several priests served as associates. Apart from those mentioned; Father Paulouse, Father Vitus, Father White, Father Ray, Father Anthony, from Nigeria, Father Biju, Father Britto, Father Lourdhu, from India also spent time in the parish. For over a year there was only one priest here and Father O’Quinn (retired) helped out in place of an associate.

In 2012, St. Stephen’s Parish took over pastoral ministry in Port-au-Port East (involving Mass on Saturday and Sunday) as well as sacramental ministry in Piccadilly (involving Mass on Sundays). St. Stephen’s Parish had also previously assumed sacramental ministry in the Parish of St. Fintan’s, offering Sunday Mass there twice a month.

After the fire of October 19, 1969, a committee was set up to plan the building of the present church. On May 29, 1971, the first Mass in the new church was celebrated and on 4 June, 1971 it was officially blessed by Bishop Richard T. McGrath.

Today the Parish has approximately 6,000 parishioners.