W 1725 parafia wchodziła w skład dekanatu kamienieckiego diecezji włodzimiersko-brzeskiej.
W 1839, w myśl synodu połockiego, parafia weszła w skład nowo utworzonej eparchii wileńskiej i litewskiej Rosyjskiego Kościoła Prawosławnego. Oprócz dwóch cerkwi w Milejczycach, parafia posiadała też cerkiew cmentarną w Sobiatynie (obecnie należącą do parafii w Sasinach). W 1847 parafia liczyła 1594 wiernych i 2 duchownych.
W 1859 w wyniku pożaru cerkiew parafialna uległa znacznym uszkodzeniom. W 1870 otwarto pierwszą milejczycką szkołę cerkiewną. W tym okresie w Milejczycach bardzo aktywnie działało bractwo cerkiewne, skupiające ok. 200 osób. W 1878 parafia liczyła 2094 wiernych. W 1887 rozebrano cerkiew św. Mikołaja (pochodzącą prawdopodobnie z 1820), z której drewno sprzedano do Zubacz celem zbudowania tam cerkwi cmentarnejWzniesiona na cmentarzu w Zubaczach cerkiew (pod wezwaniem Świętej Trójcy) istniała do 1969, kiedy to spłonęła od uderzenia pioruna.. Około 1890 wzniesiono cerkiew cmentarną pod wezwaniem św. Mikołaja. 20 czerwca 1899 rozpoczęto budowę cerkwi parafialnej w miejscu poprzedniej, nie nadającej się do użytku. Prace ukończono 8 września 1900;