The Episcopal congregation of St. Paul's in Cleveland made its third stop on its eastbound journey at the southeast corner of Case Avenue (East 40th Street) and Euclid Avenue in 1876. Founded in 1846 at the American House Hotel at Superior Avenue and West 6th Street, St. Paul's held services in rented rooms until it completed a frame church at Sheriff (East 4th Street) and Euclid Avenue. In 1851 St. Paul's built a brick Gothic church on the same site that served the congregation until 1876, when prominent members convinced church officials to build on the site further east on Euclid Avenue in the middle of Millionaires' Row.
The new Victorian Gothic structure was designed by architect Gordon Lloyd of Detroit and built by Andrew Dall of Cleveland. Berea sandstone was used to complete the cruciform plan with a 120-foot bell tower complete with exaggerated turrets and pinnacles. The interior features decorative wood trusses in an inverted ship's keel style and Tiffany stained-glass windows. Neighbors' homes at the intersection included John D. Rockefeller on the southwest corner and Jeptha H. Wade and Sylvester T. Everett on the north side of Euclid.
The first service in the new St. Paul's was held on Christmas Eve, 1876, where the city's aristocracy would come to worship. Notable socially prominent patron services were routine at St. Paul's including weddings and the funeral of Marcus Hanna attended by President Theodore Roosevelt. St. Paul's tower bell tolled to summon Cleveland's nabobs to services but the sound proved too much for some neighbors. "Some arrangement was made," wrote reporter S. J. Kelly of the Plain Dealer, in which an annual $100 contribution to the church would silence the bell for more than 15 years. In 1902, an enthusiastic bridegroom handed the janitor five dollars and the bell pealed thereafter!
The church served the congregation for 52 years until it moved again eastward to Cleveland Heights. St. Paul's sold its magnificent building to the Cleveland Catholic Diocese which re-dedicated it as the Shrine of the Conversion of St. Paul on October 2, 1931. In 1932 a convent was built on the grounds and Cleveland Bishop Joseph Schrembs invited the Franciscan Order of the Poor Clare nuns, a group that had come to Cleveland about a decade before from Austria, to establish the devotion of Perpetual Adoration and to "pray for the needs of the city" at St. Paul, a devotion which continues today. The millionaire neighborhood dissolved in the 1930s and St. Paul Shrine assumed various ministries during its ensuing 85 years as a Catholic institution.
The neighborhood surrounding the former Millionaires' Row was heavily populated during and after World War II, and the Shrine drew many worshipers to its services. In 1949, the Diocese declared St. Paul a parish to serve the community north and south of Euclid Avenue. In the early 1950s, many Puerto Rican migrants arriving in Cleveland were drawn to St. Paul's by Fr. Thomas Sebian, a Spanish-speaking priest in residence there. Along with Our Lady of Fatima Parish in Hough, St. Paul Shrine contributed to the expansion of the Puerto Rican community on the East Side before many Puerto Ricans re-centered on the Near West Side in the 1960s. The St. Paul Shrine congregation peaked in 1978 with more than 700 members, who represented a diversity of people. Continued change in the neighborhood brought varied worshipers while St Paul's maintained its vibrancy as a "way station for shorter term parishioners" and a place for those struggling with addictions or homelessness. St. Paul's welcomed the gay community and other marginalized communities to its services, leading one close observer to liken it to the "Island of Misfit Toys."
The Shrine of the Conversion of St. Paul was decommissioned as a parish in 2008 yet remains a Shrine for Perpetual Adoration of the Blessed Sacrament and a destination for faithful from around the city and the world. In fact, some of its nuns, trained through St. Paul's missions to India, are now cloistered at St. Paul's. The Shrine of the Conversion of St. Paul remains an anchor on Euclid Avenue drawing worshipers from millionaires to the homeless.