"In the year 1796, when the colored members of the Methodist Episcopal Church in the City of New York became increased, and feeling a desire for the privilege of holding meetings of their own, where they might have an opportunity to exercise their spiritual gifts among themselves, and thereby the more useful one to the other, a few of the most intelligent obtained permission from Bishop Francis Ashbury to hold meetings by themselves, in the intervals of the regular preaching hours of our white brethren, in the best manner they could." --Bishop Christopher Rush

The oldest church of the African Methodist Episcopal Zion Church denomination was called "Zion" Church. In 1796, Peter Williams, the sexton and congregant of the John Street Methodist Church, led his colored brethren from the church and severed connections with it. These men and women formed a religious body and met in a converted stable on Crosby Street. The church was chartered as the African Methodist Episcopal Church of New York City called Zion (A.M.E. Zion) in 1801. The first Zion church was built that same year in the Fifth Ward at the corner of Church and Leonard streets. The first ordained deacons and elders were Abraham Thompson, James Varick, and Leven Smith. To accommodate the rapidly growing congregation, Zion soon expanded and lengthened the church.

Although A.M.E. Zion continued under the governance of the white Methodist Episcopal Church after the congregation left in 1796, it acted as a separate and independent body. African American religious leaders were constantly under scrutiny and confronted with struggles and conflicts under the Methodist Episcopal Church. Their roles in the church were relegated to that of stewards rather than respected religious leaders. They had limited authority within the orders of the church, and they experienced racism from white preachers within the governing body. Finally, on July 26, 1820, the church members officially voted themselves out of the Methodist Episcopal Church and commenced to operate under their own Book of Discipline (a compilation of rules and laws outlining the responsibilities, activities, and conduct of member of the church). The Discipline was written under the direction of Bishop James Varick, Abraham Thompson, and William Miller and published on October 25, 1820.