The establishment of the church was undertaken after the Treaty of Riga left a large amount of territory previously under the control of the Russian Empire, as part of the Second Polish Republic. Eastern Orthodoxy was widespread in the Belarusian Western Belarus regions and the Ukrainian Volhynia. The loss of ecclesiastical link due to the persecution of the Russian Orthodox Church in the Soviet Union, left the regional clergy in a crisis moment, and in 1924, the Ecumenical Patriarchate took over establishing several autonomous churches on territories of the new states that were formerly wholly or partially part of the Russian Empire (Finland, the Baltic States, and Poland). Earlier, in January 1922, the Polish government had issued an order recognizing the Orthodox church and placing it under the authority of the state. At that time a Ukrainian,
Yurii Yaroshevsky, was appointed Metropolitan and exarch by the patriarch of Moscow. When Yaroshevsky began to reject the authority of Moscow Patriarchate, he was assassinated by a Russian monk. Nonetheless, his successor, Dionizy Waledyński (Dionisii Valedinsky), continued to work for the autocephaly of the Polish Orthodox church, which was finally granted by the Ecumenical Patriarch of Constantinople in his Tomos of 13 November 1924. Given that most of the parishioners were Ukrainians and Belarusians living in the Eastern areas of the newly independent Polish Second Republic, the Patriarch of Constantinople had a canonical basis to grant the Tomos to the Polish church as a successor of the Kyiv Metropolia, the former territory of Kyivan Rus' which Constantinople continued to see as its canonical territory (despite having agreed to allow Moscow to be its caretaker it in 1686). The Russian Orthodox Church at the time did not recognise the Polish autocephaly, as it did not recognise the autocephaly of the Orthodox Church of the Czech Lands and Slovakia.
During the interwar period, however, the Polish authorities imposed severe restrictions on the church and its clergy. The most famous example, the Alexander Nevsky Cathedral in Warsaw was destroyed. In Volyhnia a total of 190 Eastern Orthodox churches were destroyed and a further 150 converted to Roman Catholicism. Several court hearings against the Pochayiv Lavra also took place.
After the Second World War most of the ethnically Ukrainian and Belarusian territories were annexed by the Soviet Union, holding up to 80% of the PAOC's parishes and congregation, which were united with the recently re-instated Moscow Patriarchate. The remaining parishes that were now on the territory of the Polish People's Republic were kept by the PAOC, including most of the mixed easternmost territories such as around Chełm and Białystok. In 1948, after the Soviet Union established political control over Poland, the Russian Orthodox Church recognised the autocephalous status of the Polish Orthodox Church.
Although most of the congregation is historically centered in the Eastern borderland regions with considerable Belarusian and Ukrainian minorities, there are now many parishes across the country, as a result of Operation Vistula and other diaspora movements. There are also some adherents in Brazil, resulted from the 1989 canonical union between the hierarchy headed by Metropolitan Gabriel of Lisbon, formerly under the Church of the Genuine Orthodox Christians of Greece, and the Polish Orthodox Church. The European bishops, however, have left the jurisdiction in 2000, which eventually resulted in senior Bishop Chrysostom being raised to archepiscopal dignity. There are now parishes in the states of Rio de Janeiro, Pernambuco and Paraíba, plus a monastery in João Pessoa.
In 2003, following the decision of the Holy Sobor of Bishops of the Polish Autocephalous Orthodox Church, the New Martyrs of Chelm and Podlasie suffering persecution during the 1940s were canonized.