First Presbyterian Church began as a "home mission" to Dakota Territory. Isaac Oliver Sloan spent most of his life as a frontier pastor, traveling along the Northern Pacific Railway to preach and establish churches. In 1873, he helped establish a congregation in Bismarck and was elected its pastor. The Mandan Pioneer reported that "Rev. I. O. Sloan would preach at the school house" on September 11, 1880. The Mandan congregation initially met wherever space was available, including a saloon and the city's log schoolhouse. It eventually purchased property and constructed a church. Several Eastern congregations provided chairs and communion ware, and a congregation in Sloan's hometown of Philadelphia gave the church a large Bible.
The congregation was formally organized on August 21, 1881, when its first wooden church was completed near Dilworth Avenue, now Third Avenue NW, and Third Street NW. An 1883 edition of the Mandan Pioneer called it "the largest and most expensive house of worship in the city" and noted that "a large basement was furnished for a Sabbath School." C. A. Heegard served as one of the early superintendents of the church school. Sloan was appointed Mandan's pastor in 1882.
In June 1916, the original wooden church was moved across the street so services could continue while a new brick church was constructed on the original site. The cornerstone was laid in October 1916 before a large audience. The service opened with a hymn and a prayer by pastor F. W. Thompson. C. H. Brown of Christ Episcopal Church read scripture, and F. W. Gress of the Methodist Church offered greetings. North Dakota Supreme Court Justice A. A. Bruce laid the cornerstone.
A copper box placed beneath the stone contained a photograph of the old church; programs from the cornerstone ceremony and Thompson's installation; a list of church officers; and copies of the Mandan Daily Pioneer, Mandan News, and Mandan Republican. During construction, services were held in the Commercial Club rooms above the former Gambles store on Main Street.
The new church was formally dedicated with three services on Sunday, July 8, 1917. People from churches of all denominations joined the celebration. The Reverend George E. Hunt of Wisconsin was the special speaker, and Pastor Thompson officiated. The congregation admired the building's exterior, eight stained-glass windows, 350 oak seats, and richly furnished interior. The day's highlight came at the conclusion of the late-afternoon service, when the setting sun streamed through the Sloan Memorial window above the main entrance.
Other ministers included the Reverend Hugh H. Owen and the Reverend I. Scherpenisse. The $35,000 (about $880,000 in 2025 dollars) building was fully paid for when it opened. Fundraising continued, producing another $5,000 (about $93,000 in 2025 dollars) for a pipe organ installed in July 1919.
In 1957, a $60,000 (about $688,000 in 2025 dollars) south wing added two floors of classrooms, a small chapel, church offices, and a pastor's study. The Reverend John Kuyper and Mrs. Lyon Cary, a parish member since 1889, hosted the groundbreaking ceremony. George Toman was school superintendent. Gilbert W. Stewart had served as pastor for the preceding 25 years. Ed Toman chaired the Building Committee, and W. A. Wise chaired the Education Committee.
The Reverend A. Benjamin Dove Jr. became pastor in September 1959. He and his wife, Barbara, moved to Mandan from Minnewaukan, North Dakota. Dove served the congregation for more than 30 years. In 1968, Sunday school rooms on the east side of the 1916 building were remodeled as Stark Hall. A new chancel and $25,000 (about $219,000 in 2025 dollars) pipe organ were dedicated on May 11, 1969. In 2014, church members renamed and rededicated the Dove Educational Wing in recognition of the Doves' service.