On November 16, 1870, the St. Paul's Norwegian Evangelical Lutheran Congregation was formed under guidance from Peder L. Asbjornsen, pastor of the Bostwick Valley congregation. The newly formed group counted 38 charter members and elected C. H. Walgeford as deacon; Simon Christoffersen and Gustaf Adolph Quarford as trustees. In April of the following year, a house of worship was purchased "somewhere on 8th Street" which was known as "Spiritual Hall." The building was later moved to a leased lot on North 11th Street between Pine and Badger Streets which was purchased in 1876. In 1882 a building was purchased from the Presbyterians near 6th and King Street for $3,500.

In October of 1871, the congregation called Pastor Asbjornsen to serve them. He ministered to the congregation until 1875 when Rev. Egil H. Midtbo was called to serve. By this time, the membership rolls counted 49 souls and Sunday School began. The congregation also became part of a parish with La Crosse, Bostwick Valley, Houston (Minnesota) and Looney Valley (Minnesota). Several pastors came and went between 1880 and 1894 when Rev. Rasmus Andersen preached his own installation sermon. Pastor Andersen died in 1914 and many changes occurred during his tenure. A new facility was constructed on the southwest corner of West Avenue and Division Street and services were first held there Christmas Day in 1896. The parish formed in 1880 was dissolved and St. Paul's and Eden congregation in Galesville formed a parish. This relationship was dissolved in 1918 and St. Paul's became an independent congregation holding worship services every Sunday. Rev. Andersen's successor, Pastor O. C. Myhre, began using the English language in the weekly services. In 1920, under the leadership of Rev. H. T. Braa, the congregation voted to have one service a month in Norwegian and all other services to be conducted in English. By 1940 Rev. Mars A. Dale used English exclusively in worship services. In 1942, the constitution was revised and the name was officially changed to St. Paul's Lutheran Church of La Crosse, Wisconsin. Again, many pastors had come and gone during this time.

In 1953, Rev. Arthur M. Feroe became pastor of St. Paul's serving 31 years--the longest of any senior pastor for the congregation. A new Parish House and Chapel were completed in 1956 and ground-breaking services for a new church building were held in 1960. The dedication took place in December 1961. The old building was razed and a parking lot constructed on that site. "Damascus Illumination," a two-piece sculpture by artist Paul T. Granlund, was placed in front of the church in 1966. By 1970, the congregation numbered 1,400 baptized members. After Rev. Feroe retired, Rev. Arnold J. Athey was installed as pastor in early 1985. At the time of the disbanding in August 2019, retired Rev. Ted DeWald took care of the spiritual needs of the congregation.