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 ecclestical 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 formally wholly or partially part of the Russian Empire (Finland, the Baltic States, and Poland).
During the interbellum, 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 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 POC's parishes and congregation. These 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 POC, these included most of the mixed easternmost territories such as around Chełm and Białystok. In 1948 under pressure from the Russian Orthodox Church, the Ecumenical Patriarchate granted the POC autocephalous status.
Most of the congregation is still centered in the Eastern borderland regions with considerable Belarusian and Ukrainian minorities. In total, it has approximately 600,000 adherents.
In 2002 following the decision of the Holy Sobor of Bishops of the Polish Autocephalous Orthodox Church canonized the New Martyrs of Chelm and Podlasie suffering a persecution during the Fourth Decade of the Twentieth Century.