During the Civil War, black religious activities were highly regulated, owing to fears that slaves would leave to serve in the Union Army. After the war, racial tensions between blacks and whites facilitated the establishment of black churches. St. Paul AME came about as the result of an AME minister's efforts to organize black members of the Methodist Episcopal Church South (today Blacksburg United Methodist Church). White methodists wanted to help the new St. Paul AME and shared their building.
Today's St. Paul AME was constructed in 1901 on the site of a previous AME church, no longer extant. A few years later, the building was coated in stucco. This church still houses an active congregation today.