W XV wieku wieś Milejczyce była zasiedlona przez bojarów książęcych. Pierwsza znana wzmianka historyczna, pochodząca z 1479 roku, dotyczy Sienki z Milejczyc, z powiatu brzeskiego.
W 1510 roku Milejczyce wchodziły w skład dóbr królewskich. Król Zygmunt I Stary (1506-1548) w 1516 roku nadał tej wsi prawa magdeburskie, tworząc tutaj miasto królewskie, aby rozwijać trakt biegnący z Mielnika do Bielska. Kolejni królowie polscy byli też kolatorami miejscowego kościoła. W 1524 r. plebanem w Milejczycach był ks. Maciej Korwin. Dnia 30 października 1529 roku król Zygmunt I ufundował tutaj drewniany kościół pw. św. Zygmunta, św. Stanisława Biskupa i Męczennika i św. Mikołaja. Oryginalny dokument fundacyjny jest obecnie przechowywany w Bibliotece Narodowej Litwy w Wilnie. W 1556 roku świątynia ta została rozebrana przez mieszczan, a na jej miejscu wzniesiono nową. Funkcje plebanów pełnili: w 1560 - ks. Jan Kalekut, w 1568 roku - ks. Sebastian Jelitowski, w 1573 roku - ks. Sebastian Jaktorowski. W czasie „potopu szwedzkiego” w 1657 roku kościół został doszczętnie spalony przez Szwedów i Kozaków.
Kolejny kościół został wzniesiony po 1650 roku na ruinach spalonego w tymże roku, staraniem ks. Pawła Krasnodębskiego, ówczesnego proboszcza milejczyckiego (od 1639-1677). Jego fundatorem był Gothard Wilhelm Butler (ok. 1600-1660), podkomorzy nadworny koronny i major straży przybocznej króla Jana Kazimierza. Po trzecim rozbiorze Polski (1795) parafia została przecięta granicą i w części przyłączona do parafii siemiatyckiej (Pokaniewo, Zabłocie).
Obecny, drewniany kościół był trzykrotnie remontowany w: 1782, 1829 i 1856 roku. Po upadku Powstania Styczniowego w dniu 20 lutego 1866 roku został zamknięty, a budowle i grunty przekazano służbie cerkiewnej. W tym samym roku - z rozkazu (nr 427) z dnia 11 kwietnia Konstantego von Kaufmana (1818-1882), generał-gubernatora grodzieńskiego i wileńskiego (1865-1866) - świątynię zamieniono na cerkiew prawosławną pw. Świętego Ducha. Podobny los spotkał kaplicę w Chlewiszczach, która 26 sierpnia została zamknięta i przerobiona na filię prawosławnej parafii pw. św. Aleksandra Newskiego w Połowcach - z rozkazu (nr 2659/1864) wydanego przez Michała hr. Murawjewa „Wieszatiela” (1796-1866), generał-gubernatora litewskiego (1863-1865).
Rewindykacja kościoła nastąpiła dopiero po zakończeniu I wojny światowej w dniu 17 maja 1917 roku. Ponownej erekcji parafii dokonał w dniu 4 lipca 1921 roku, ks. abp Jerzy Matulewicz (1871-1927), biskup wileński (1918-1925). Jej pierwszym administratorem (1921-1926) został ks. Stanisław Pietkiewicz (1889-1943).
W narożniku cmentarza kościelnego stoi dwukondygnacyjna, drewniana dzwonnica konstrukcji słupowo-ramowej, wzniesiona w 1740 roku.
Obok kościoła znajduje się drewniana plebania zbudowana ok. 1900 roku.
Kaplica:
Pokaniewo - Drewniana kaplica pw. Nawiedzenia NMP została zbudowana w latach 1984-1985, staraniem ks. Antoniego Zajączkowskiego (1944-1990), ówczesnego proboszcza (1984-1987), według projektu inż. Stanisława Szymańskiego z Gdańska. Jej poświęcenia w dniu 22 czerwca 1986 roku dokonał ks. bp Władysław Jędruszuk (1918-1994), administrator apostolski diecezji Pińskiej (1967-1991).
Oprac. ks. dr Zbigniew Rostkowski
