In 1873, several inhabitants of Freedman's Town, a community of recently freed people just north of the Dallas city limits, met with Methodist Ministers Rev. H. Oliver and Rev. William Bush under a brush arbor to organize the area's first African American Methodist Episcopal Church. Oliver became St. Paul's first pastor. Dallas Postmaster Anthony Norton donated the first church site upon which the congregation built a small frame sanctuary, which was also used as a school for African American children. In partnership with the Perkins School of Theology, the church provided training for African American ministers. Samuel Huston College (later Huston-Tillotson University), organized in 1876, held its first classes at the church.Marker is Property of the State of Texas
In 1901, the congregation began constructing a new brick-clad sanctuary by digging and finishing a concrete basement, called "Noah's Ark," where services were held during the 26 years it took to complete the sanctuary. Construction proceeded fitfully as material became available. Tradition holds that the façade has five different shades of brown brick because, for many years, parishioners brought bricks for the offering. Finally completed in 1927 under the leadership of Pastor George Deslandes, the sanctuary cost $80,000. The Gothic Revival style was derived from a design by William Sidney Pittman, Dallas' first African American architect. Although around 1950 highway construction began to demolish the North Dallas neighborhoods served by the church, St. Paul endured as a political, cultural and spiritual center under the leadership of Pastor I.B. Loud (1948-1980) and his successors.