The first known Anglican service in the area was conducted in 1871. The service was held in the house of Charles Morley just north of the future settlement of Huntsville, led by an English Missionary to a congregation of seven people. When the Diocese of Algoma was created in 1873, a log building in Huntsville became jointly used by the Anglican congregation and the Orange Lodge. In 1876, the first settler of Huntsville, William Cann, donated land by the Muskoka River to the parish. Here the first church of the settlement was erected, in 1894 this church was burned down in a fire.

In 1883, the Rev. Thomas Llwyd was appointed the first rector. He bought the present rectory, and saw that another Hall was built with a driving shed for horses. In 1886, land was bought for a cemetery. In 1889, the Rev. Llwyd hoped that a stone church could be built and plans were began in 1894, accelerated by Huntsville’s "Great Town Fire" which had destroyed the wooden hall.

On June 5, 1895 the first service was held in the new church. The new church was consecrated by Bishop Thorneloe in 1900. Before his death in 1903 the Rev. Llwyd persuaded the parish to build a stone Parish Hall. In 1906 this Parish Hall became a keystone of Huntsville, hosting the first slide shows, traveling shows, a Toronto Opera company, and eventually movies in the area.

Throughout 1925-1926, the sanctuary and chancel were enlarged, and the church stable behind the rectory was torn down. In 1964, under the guidance of Canon George Sutherland, the chapel was built and an addition to the organ loft, so the new pipe organ could be installed.  The new organ, chapel, and furnishings were dedicate by The Most Rev. W.L. Wright on November 1, 1964.

In 1989, All Saints’ Church Parish Hall, which had been erected 1905, was named Sutherland Hall in celebration of the 40th anniversary of the Rev. Canon George Sutherland, honouring both he, and his wife Jean for their devoted service to the church. In 1992, the parish, under the guidance of Archdeacon Eric Patterson, purchased the old Francis property adjacent to the church, to house the church office, church school, and meeting space. This house had been designed and built in 1904 by William Proudfoot for parishioner Frederick Francis. In 2000, significant modifications to Sutherland Hall were made to make it wheelchair accessible, including a new power-entry door, an elevator between the Upper and Lower and Entry levels, and new washrooms on the upper Level.

Incumbents of the Parish of All Saints' Huntsville include: the Rev. Thomas Llwyd (1883-1903), the Rev. W. Balfour (1903-1911), the Rev. E. J. Harper (1911-1914),
the Rev. P. S. R. Law (1914-1925) 
the Rev. P. Steed (1925-1926),
 the Rev. N. F. Smith (1927-1934), the Rev. E. R. Nornabell (1934-1948), the Rev. J. E. Hinchcliffe (1948-1954),
 Canon G. W. Sutherland (1954-1990), the Ven. Eric Paterson (1992-1996), 
the Ven. Lynn Uzans (1996-2001), the Ven. Dawn Henderson (2002-2019), the Ven. Kelly Baetz (2020).

Sources:

• All Saints Huntsville, http://www.allsaintshuntsville.ca/history.htm [accessed 2013 August, 7]
• "Celebration at Huntsville Well Attended", The Algoma Anglican 4, no. 4 (1960): 8.
• "Organ, Chapel, Dedicated At Huntsville", The Algoma Anglican 8, no. 11 (1964): 4.
• "All Saints in Huntsville erects an entrance gate to church", The Algoma Anglican 20, no. 10 (1976): 7. Algoma University Archives, 2013-086_001_010_023.
• Esther Spender and Dr. Noreen Spencer-Nimmons, "All Saints' Anglican Church: Huntsville, Ontario", 1998, All Saints' Anglican Church (Huntsville, Ont.) sous fonds, Algoma University Archives, 2009-227_001_002.