Apostles' current building at 1520 Bull Street was originally occupied by the Second Calvary Baptist Church, a historically African-American congregation.

Chip Edgar, a former Episcopal Church priest in Illinois, was the founding rector, leading a group of 25 parishioners.

[3] After Second Calvary vacated the Bull Street building, Apostles purchased it and renovated the church, occupying the space for worship services in 2011.

[2] In 2016, Apostles raised $1 million toward a building expansion and program funds and tithed $100,000 to the Rwandan Anglican church.

In 2016, the PEARUSA Southeast Network dissolved and Church of the Apostles joined the Diocese of the Carolinas, where it was designated as the diocesan cathedral and Edgar as dean.