The first service in this area was in approximately 1816 in a barn east of where the current church stands and was on the property of Gilbert Bastedo. Bastedo established a farm on Dundas Street in 1806. As a devoted Presbyterian, he offered the use of his home for worship when a travelling preacher came through the area.

In 1822 the congregation was constituted and Bastedo donated land on his farm for a church, St. Paul's Presbyterian Church.

The Reverend King, a missionary sent to Canada who had settled on a farm in Nelson Township around 1819, in the area where Walmart currently stands, was the first minister.

The Brant family, especially John Brant and Elizabeth Brant Johnson, and the Bates family, were motivating forces behind the establishment of this parish. Martha Tassie, daughter of David Tassie, stonecutter, was recorded as the first child baptized there on November 15, 1835, by Reverend Mack. The first recorded marriage was that of Elizabeth Sinclair and William Walton by special licence on December 28, 1835.

The church currently located on Dundas Street is the second building and was erected in 1867. This historic church building still stands beside the new church building today.