A group of members of Monumental Episcopal Church began planning St. Paul's in 1845. The new congregation appears to have been architecturally conscious and went on a tour of the Northeast to seek ideas. They especially admired St. Luke's Episcopal Church in Philadelphia and commissioned the designer of that church, Stewart, to provide a Richmond version. Many of the features of the Stewart design remain intact, including the Corinthian portico and the steeple. The cast iron capitals that top the stuccoed brick columns are one of the first uses of cast iron ornament in Richmond. The Gibbs-influenced steeple originally supported a Gothic-like octagonal needle spire. Along the sides of the buildings are large Corinthian pilasters and a continuation of the full entablature of the pedimented portico.
In the 1890s the large central pulpit was removed and the shallow apse expanded to its present configuration. The gallery, supported by slender cast iron columns, is original. Ornament in the Corinthian order is used throughout the sanctuary, including pilasters, columns, and coffered panels along the gallery and in the plaster ceiling. The most spectacular feature of the ceiling is the large sunburst panel in the center. The prominence of the church in the history of the Confederacy (President Jefferson Davis, General Robert E. Lee, and other notables worshiped here) resulted in a large number of memorials in the sanctuary, including a window and an altar mosaic by Tiffany Studios.
To the east of the sanctuary is a parish house complex which includes a courtyard, an atrium, and parking garages on 8th Street. The complex is one of Richmond's most sophisticated examples of classicism from the second half of the twentieth century. Significantly, the congregation rejected the original modernist proposal in favor of the current design. The 1992 renovation created an atrium and remodeled the undercroft.