St. Paul's Episcopal Church emerged in 1846, beginning in rented space until its first dedicated building opened in 1848 at the corner of Sheriff Street (now East 4th) and Euclid Avenue on the site of the present-day House of Blues. Following a devastating fire, the church rebuilt a brick Gothic edifice that opened three years later. As commercial expansion accompanied the emergence of downtown Cleveland in what had formerly been a compact walking city, St. Paul's moved in 1876 to a newly built Gothic church at the corner of Case Street (now East 40th) and Euclid, squarely within Cleveland's famed "Millionaires' Row." This church was designed by Gordon W. Lloyd, an English-born Detroit architect who also designed many other Episcopal churches in the Midwest. At its new location, St. Paul's expanded impressively and even spawned several other new congregations as it grew.
By the 1920s many St. Paul's parishioners had moved eastward into the nearby suburbs of Cleveland Heights and Shaker Heights. In 1928 the church followed suit, choosing a site on the eastern edge of Barton Deming's Euclid Golf allotment at the corner of prestigious Fairmount Boulevard, the "Euclid Avenue of the Heights," and Coventry Road. The new building, designed by J. Byers Hayes of Walker and Weeks in the English Gothic style, was erected of Indiana limestone. On its departure, its previous building was sold to the Catholic Diocese of Cleveland and reopened in 1931 as St. Paul's Shrine of the Blessed Sacrament. In more recent years the building has served as home to multiple Catholic orders rather than as a diocesan church.
In Cleveland Heights, St. Paul's continued to grow, but its building remained unfinished, a casualty of the onset of the Great Depression. Originally to include a large nave for worship services, St. Paul's made do until 1951 with holding services in its parish hall. By the time the church raised sufficient funds to build the Gothic nave it had envisioned back in the 1920s, its leaders opted instead to follow an emerging trend toward fashioning naves in the manner of the early Christian church, in which ornamentation was spare and the altar was moved closer to the congregation.
By the early 1960s St. Paul's flourished under the energetic leadership of Dr. Chave McCracken. During McCracken's tenure as rector, St. Paul's became more consciously inclusive. In spring 1963 it hosted Dr. Martin Luther King Jr., who gave one of the speeches leading up to his famed Lincoln Memorial address later that year. Church membership reached its peak in the 1960s, with the main Sunday service splitting into two services to handle the growing parish. Years later, following a downward trend in the Heights population and in membership in mainline Protestant denominations, St. Paul's returned for a time to a single service. More recently, it restored the separate services as part of a determined effort to attract young families.
Today St. Paul's remains a vibrant part of Cleveland Heights and, with some 1,800 parishioners, is the largest Episcopal congregation in the Diocese of Ohio.