Arthur Gilman had just begun his career when he was hired in 1844 to design St. Paul's Church, a wood Gothic Revival structure that burned in 1857. The Episcopal church immediately hired Gilman again to design the Gothic replacement, constructed of pink Dedham granite. Gilman's Gothic Revival design was inspired by small masonry churches by Richard Upjohn, a New York architect he greatly admired. Upjohn's small parish churches featured a nave flanked by an almost freestanding tower and exposed trusses on the interior. In his published writings Gilman expressed a preference for the use of sandstone over granite for Gothic architecture, but he must have found acceptable the softer and darker tones of the pinkish-brown Dedham granite.
The tower of the church was not completed until 1869, and a chapel was built six years latter. Although it is traditional to add the chapel to the existing church, St. Paul's Chapel was built as a separate brick structure across the street. The architects, Gridley J. F. Bryant and Louis P. Rogers, had worked with Arthur Gilman on a number of major projects in Boston during the 1860s.