Prostiet ble opprettet Ved kgl.res. av 22. august 1749 ved utskillelsen av Mellem Borgesyssel prosti fra det opprinnelige Øvre Borgesyssel prosti. Da ble prestegjeldene Aremark, Askim, Eidsberg, Rakkestad, Rødenes og Trøgstad skilt ut fra Øvre Borgesyssel prosti som eget prosti:[2]
[Kongelig] Rescr. [af] 22. Aug. [1749] (til Bisk. over Agershuus Stift), at Øvre Borgesyssels Provstie skal deles i tvende Provstier, det Ene, hvilket herefter som tilforn skal kaldes Øvre Borgesyssels Provstie bestaaende af de paa denne [vestre] Side af Glommen beliggende syv Præstegjelde: Nesodden, Aas, Westby, Krogstad, Haabel, Spydeberg og Skibtvet; det Andet, der skal kaldes Mellem Borgesyssels Provstie, indbefattende paa den anden [østre] Side af Glommen beliggende seks Præstegjelde: Askim, Eidsberg, Rakkestad, Trøgstad, Rødenæs og Aremark.
Ved lov av 10. mai 1968 om deling av Oslo bispedømme, ble det opprettet et Borg bispedømme bestående av Østfold og Akershus fylker med unntak av Asker og Bærum kommuner. Ved kgl. res. av 25. juni 1971 med virkning fra 1. januar 1973 ble det foretatt endinger i prostiinndelingen i Borg bispedømme. Mellom Borgesyssel prosti fikk navnet endret til Østre Borgesyssel prosti.[3] Ved kommunereformen 1. januar 2020 ble kommuner og fylker omorganisert, og sogn ble overført mellom prostiene.
