Born in Charleston, South Carolina into a Baptist family, Paul Washington later graduated from Lincoln University and Philadelphia Divinity School. Upon completion of his pastoral work at the Church of the Crucifixion in South Philadelphia, Pennsylvania, Washington married his wife Christine. They moved to Liberia as missionaries in 1948. During his six years in Liberia, Washington helped found Cuttington College, which educated many African leaders. After returning to the United States, Washington assumed the position of rector at the Church of the Advocate in Philadelphia, a position he held for twenty-five years (1962-1987).

As a supporter of the Black Power movement and the Black Panthers, Washington offered his church as a meeting place for groups working towards equality and justice. The Church of the Advocate hosted the Black Power Convention in 1968, a gathering that drew the leading Black activists of the time. Two years later he welcomed the National Convention of the Black Panther Party. Washington became accustomed to the criticism he received for his controversial beliefs, including his demand that Episcopalians pay reparations to the descendants of enslaved people. From 1964 to 1971, he served on Philadelphia’s Human Relations Commission.

Under Washington’s guidance, the Church of the Advocate became a beacon of liberation for those marginalized in the wider church. In 1974, the church hosted the ordination of the “Philadelphia 11", the first women irregularly ordained in The Episcopal Church. This action galvanized the church to confront the issue, ultimately allowing women into the priesthood in 1977.

While at the Church of the Advocate, Washington also served as Episcopal Chaplin at Eastern State Penitentiary and on the MOVE Commission, a radical “back to nature group” following the teachings of the self-styled John Africa. Washington was the chaplain of the Advocate Communities Development Corporation’s (ACDC) Board of Directors and continued to serve ACDC until the fall of 1998. Established by his wife, ACDC continues to provide low and moderate-income housing to the members of the North Philadelphia community.

Washington's insight into the struggles for justice and dignity in the latter half of the twentieth century is documented in his autobiography Other Sheep I Have.