In 1857, a group of seven people gathered to organize the parish named St. Mary's Episcopal Church. In July the Rt. Rev. Henry W Lee, first Bishop of Iowa, confirmed a class of five. In the early years, services were held at Curlew House, in the courthouse, and over a dry goods store.
In 1865 the cornerstone of St. Mary's was laid on the corner of Market and Fourth streets. The church was consecrated in 1879 and 196 communicants were present. In 1880 a pipe organ was purchased for the church, the finest in town, but unfortunately, no one at the church could play it. They hired Miss Emma Holt from New York to come and be the organist.
By 1890, the congregation had grown to the point where six services were needed for Easter Day. The congregation had outgrown the church building. In 1894 the name of the church was changed to Trinity. They laid the cornerstone for the new building on August 30 at the corner of Market and Fifth streets.
Edward Hammett designed the new building. He had also designed churches in Davenport and Sioux City. He designed a Gothic Revival style building, composed of rusticated limestone and featuring Gothic arch windows and doors throughout. On April 28, 1895, Trinity Church was consecrated by Bishop Perry.