The history of Methodism, and subsequently the United Church, in Newfoundland dates back to 1765. However, early Methodists were without a minister until 1791 and a church until 1815. Until the construction of their own church, the Methodists used the Congregational church for their services.

In 1815 the Methodists completed a church, but a fire a year later on February 12, 1816, destroyed it. The next church lasted until 1856 when they built a larger structure. The Great Fire of 1892 claimed the third church. In response to the disaster, the congregation sought the advice of English architect Elijah Hoole. They wanted him to design a distinctive church that would rival both the nearby Roman Catholic and Anglican Cathedrals. A Romanesque Revival church with some Gothic attributes was the product of Hoole's efforts.

While workers were building the new church, the congregation erected a "tabernacle" to hold services. Construction began in 1894 and took two years to complete. Inspired by eleventh and twelfth centuries Continental European Romanesque structures in Germany and Northern Italy, Hoole combined various elements in the new structure. The church is set apart by the use of red Accrington brick and panels of terra cotta ornaments on the building's exterior. There were also Gothic elements such as the spire in the southeast corner, however these were removed due to damage in 1935. The church's interior hammerbeam roof was also Gothic inspired, drawing on English examples from the fifteenth to seventeenth centuries.

Workers completed the present day Gower Street United Church in the fall of 1896. On October 4, Rev. Dr. John Potts, Educational Secretary with the Methodist Church of Canada led the consecration service. Also there was Rev. William Swan, ex-president of conference, and Rev. Levi Curtis, who was the new minister of the church. Newfoundland's world renowned opera singer Georgina ("Marie Toulinguet") Stirling also treated the congregation to several solos.

Since its opening, the structure has undergone some secondary modifications. Both gas and electrical lights originally provided lighting. When electricity became a more reliable source in the 1920s, they removed the gas fixtures. In 1930 a large Casevantes pipe organ caused a modification in the choir gallery. Stained-glass windows were also added to the building.

The Gower Street United Church became a Registered Heritage Structure in September 1995.