Methodism was first established in southeastern Virginia in 1772 under the auspices of the Methodist Society in the Norfolk-Portsmouth circuit. The church occupied two other sites in Portsmouth before the current location was purchased in 1831. A brick church, housing both white and black congregations, was erected two years later, but in 1856–1857 the latter group built its own house of worship, eventually affiliating with the African Methodist Episcopal Church. The present building was erected in 1873–1876 to the designs of Albert L. West, a practicing Methodist who received numerous commissions from congregations throughout Virginia and North Carolina. West's Gothic structure looks back to the decades of the 1840s and 1850s and specifically to Thomas U. Walter's Gothic Revival Freemason Street Baptist Church in Norfolk. The stucco-over-brick church is oriented east to west with a central tower and steeple facing Dinwiddie Street. Attached buttresses alternate with lancet windows along the nave.