On January 26, 1883, a group of thirty-five neighbors who were deeply interested in establishing the Protestant Episcopal Church in Newton Highlands met at the residence of James Simpson and formed the Association of the Parish of St. Paul. The next Sunday, the first service was held in a meeting hall at the corner of Walnut and Lincoln streets. At three o'clock that afternoon, "although the weather was unpleasant and the walking very bad," 118 people attended while the Reverend George W. Shinn, Rector of Grace Church, Newton officiated. The first offering totaled $18.55.

On the first day of May, 1883, ground was broken for a chapel at the corner of Walnut Street and Lake Avenue. On Thursday, July 19, 1883, an opening service was held in the new chapel. Cost of the chapel was $4,100, including the land, and the new parish began life with a mortgage for $1,500.

In 1888, the parish purchased the land on which the present church is located for the construction of the first rectory. Within the next decade, additions were made to the chapel and an organ fund started. But the growing parish had outgrown the chapel by the turn of the century.

In 1902, the rectory was moved to Columbus Street and the chapel was rolled across Walnut Street on logs to where the church stands today. The chancel was enlarged, and the left transept was built to provide a connection to the proposed parish house. The first service in the new church was held on Sunday, October 12, 1902.

Three years later, the parish hall was built and was, at least to some extent, equipped with electric lights. Complete confidence in this new form of illumination seems to have been lacking as gas fixtures were installed throughout and still remain.

Two other Newton parishes developed as offshoots of St. Paul's: Trinity Church in Newton Centre was established in 1889 and the Church of the Good Shepherd in Waban in 1893.

St. Paul's parishioners have long taken pride in their contributions to the life of the community and the Diocese. During the late 1930's members of St. Paul's traveled with a pageant to many Eastern Massachusetts churches. From 1967 to 1982, St. Paul's offered temporary housing to those in need as part of Christian outreach.

Since its founding, St. Paul's has had fourteen rectors. The Reverend John Balcom served for twenty nine years from 1953 to 1982. During his tenure, a unique ecumenical Christian education day school was established in conjunction with the neighboring Congregational church. Weekday classes continued for many years in the meeting rooms of both churches.

Upon Reverend Balcom's retirement in 1982, Reverend Flora Angel Keshgegian served as Interim. Reverend Keshgegian introduced the new Prayer Book and made it relevant to present day worship.

In December 1982, the Reverend Thomas W. Bauer was called as St. Paul's twelfth rector. He rejuvenated the Sunday school and produced children's festival pageants to attract young families into the parish. He also organized improvement of the physical plant and oversaw the celebration of the parish's 100th anniversary.

After completion of his doctorate at Harvard in 1987, Doctor Bauer followed a call to be headmaster at Grace and St. Peter's School in Baltimore, Maryland. The Reverend Walter Witte was named Interim.

In 1988, the Reverend Julie Norton was called as Rector of St. Paul's. During her tenure, a new organ was installed. The parish's first female senior warden was selected. Social action programs were expanded to include new outreach areas and environmental concerns. Fellowship opportunities were greatly expanded. Julie's annual colorful banner-narrative sermons at Easter and Christmas were highlights of her years at St. Paul's. Christmas Eve 1994 was her last service before accepting a call as rector of Grace Church, Crismont, Keswick, Virginia. The Reverend J.C. Woods, Jr. was chosen as Interim.

In August 1996, the Reverend Dr. Maureen Dallison Kemeza was called as the fourteenth rector of St. Paul's. During her tenure, the parish sponsored many seminarians and was very supportive of their formation for ordained ministry. Many attended the ceremonies and celebrations when the seminarians were ordained. In 2002, the parish held a successful capital fund drive to support building improvements and raised about $155,000, including $45,000 taken from existing reserves. In 2003, the parish expanded its important outreach work during the last two years to support Mission Belize to help the Anglican Diocese of Belize to build schools. Summer of 2004 saw the completion of the organic meditation garden, a space for outdoor worship and for the reflective use of the surrounding community. April 1, 2005 was Maureen's last service before resigning from the parish. She is now serving as the Priest-in-Charge at Emmanuel Church in Boston.

The Reverend Dr. Carol Flett was named Interim in April 2005.