Mielnik jest najstarszą historycznie udokumentowaną parafią prawosławną na Podlasiu. Eugeniusz Gołubiński w „Historii Cerkwi Ruskiej” podaje, że już w końcu XI w. w Mielniku była murowana cerkiew, a w niej cudowna ikona Spasa Izbawnika. Potwierdza to Kronika Ipatiewskaja, w której w 1260 roku odnotowano: „I jecha Wasilko za brata i prowadi jeho do Bresta i posła za nim ludi swoja i pomolisia Bohu Swiatomu Spasu Izbawniku jaże jest’ ikona w gorodie Mielnice i obiszczasia Daniło ukrasit’ ju”. Do końca XIII w. Mielnik pozostawał we władaniu książąt halickich. Książę Daniło (Daniel), o którym wspomina kronikarz, po przegranej z Tatarami musiał zgodnie z wolą zwycięzcy, skierować swoje wojska przeciwko Litwie. Przed wyruszeniem w bój, jego brat Wasylko zatrzymał się w mielnickiej cerkwi Bogarodzicy, aby pomodlić się przed cudowną ikoną.
Na podstawie fragmentarycznych danych wiadomo, że w końcu XIV w. istniały w Mielniku już dwie cerkwie prawosławne, stanowiące dwie oddzielne jednostki administracyjne nazywane później parafiami: Narodzenia Bogarodzicy i Zmartwychwstania Pańskiego. Ta druga przetrwała do 1836 roku. Czterdzieści dwa lata później cerkiew Zmartwychwstania, ze względu na kłopoty natury ekonomicznej, została przeniesiona na Św. Górę Grabarkę i tam poświęcona pod wezwaniem Przemienienia Pańskiego. Obecnie miejsce na terenie Mielnika, na którym stała cerkiew Zmartwychwstania nosi nazwę Woskresienskoj Horki i jest tam postawiony krzyż, natomiast parafia Narodzenia Bogarodzicy istnieje do dziś. W końcu XVIII w. liczyła ona 1103 osoby.
W 1777 r., jak głosi tradycja, rzeką Bug przypłynęła ikona Opieki Matki Bożej. Parę miesięcy później, specjalnie dla niej, zbudowano odrębną kaplicę, która po dziś dzień stoi na prawosławnym cmentarzu.
5 maja 1812 roku „umarł w Bogu wielebny Jakub Bielawski”, długoletni proboszcz mielnickiej parafii Narodzenia Bogarodzicy. Zgodnie z ostatnią wolą batiuszki wszystkie jego oszczędności zostały przekazane na budowę nowej parafialnej świątyni. W 1821 r. rozpoczęto budowę murowanej cerkwi, którą ukończono po dwóch latach. Pracami kierował ówczesny proboszcz o. Florian Zinkiewicz.
W latach 40. XIX w. nastąpił masowy powrót unitów do Prawosławia. W związku z tym znacznie wzrosła liczba wiernych i w roku 1878 wynosiła ona 1852 osoby.
W drugiej połowie XIX w. na Górze Zamkowej w Mielniku wzniesiono kaplicę św. Aleksandra Newskiego. Z uwagi na lokalizację, przeznaczona była głównie dla młodzieży. Początkowo odbywały się w niej wieczernie, później już tylko raz do roku uroczysty molebien w dzień święta patrona. Kaplica została zburzona w 1931 roku.
Na przełomie XIX i XX w. Mielnik liczył 1252 mieszkańców: 845 prawosławnych, 250 katolików i 157 żydów. Dobrze rozwinięte było szkolnictwo. W 1905 r. na terenie parafii istniało sześć szkół cerkiewno-prichodskich: w Moszczonie, Kudeliczach i Maćkowiczach oraz w Radziwiłówce, Mętnej i Mielniku, gdzie dodatkowo były szkoły: narodnaja i gorodskaja.
Proboszcz Włodzimierz Sosnowski przeprowadził gruntowny remont cerkwi: dobudowano dzwonnicę i wykonano nowy ikonostas. Po wybuchu pierwszej wojny światowej większość prawosławnych wraz z duchownymi została ewakuowana w głąb Rosji. Zabrali ze sobą co cenniejsze ikony i utensylia. W opuszczonej cerkwi i kaplicy Niemcy urządzili wojskowy szpital. Po wojnie większość mielniczan wróciła w rodzinne strony i na nowo zaczęto organizować życie parafii.
W okresie międzywojennym aktywnie działało w Mielniku bractwo cerkiewne. Wiele troski o należyty stan świątyni okazywała parafianka Olga Karpowicz, która w 1935 r. została nagrodzona „błagosłowienną gramotą”. W latach 30. parafia zamówiła w Poczajowie szereg ikon, m.in. Serafina z Sarowa. Na stację do Siemiatycz dotarły one koleją, dalej niesione były pieszo.
W tym czasie nabożeństwa uświetniał chyba najlepszy chór w całej dotychczasowej historii. Wybuchła II wojna światowa. Do Mielnika weszły wojska radzieckie i niebawem zarządziły one ewakuację z przygranicznego pasa o szerokości 800 metrów (granica przebiegała wzdłuż Bugu). 22 kwietnia 1940 r. wszyscy mieszkańcy Mielnika musieli opuścić osadę. W cerkwi i kaplicy urządzono punkty obserwacyjne. 27 czerwca 1941 r. artyleria niemiecka ostrzelała Mielnik, nie oszczędziła też świątyń. Pociski uszkodziły dzwonnicę i dach. Po przejściu frontu mieszkańcy powrócili i podjęli się remontu cerkwi, który ukończono 1 sierpnia 1943 roku. Uroczystej konsekracji dokonał władyka Benedykt. Zachował się antymins z jego podpisem „Smiriennyj Wieniedikt, Archijepiskop Biełostockij i Grodnieńskij, Egzarch Biełaruskoj Prawosławnoj Cerkwi w Vostocznoj Prusii.”
Po wojnie, po o. Janie Antiporowiczu, parafię w Mielniku objęli kolejno: o. Włodzimierz Bliźniuk i o. Eugeniusz Naumow – były więzień obozu koncentracyjnego. W tym czasie znacznie uszczuplił się majątek cerkiewny. Na rzecz skarbu państwa przeszły: kopalnia kredy o powierzchni 4 ha i 116 ha ziemi. Długo sprzeciwiał się temu o. Eugeniusz Naumow. Parafia zmniejszyła też swój zasięg terytorialny: Homoty, Pawłowicze i Oksiutycze znalazły się w grabarskiej parafii.
Na mocy dekretu z dnia 27 kwietnia 1966 r. proboszczem parafii w Mielniku został o. Eugeniusz Niesteruk. Przejechał z Bończy i właśnie rozpoczął studia zaoczne w Moskiewskiej Akademii Teologicznej. W skład parafii wchodziły następujące wsie: Mielnik (prawa miejskie utracił w 1936 r.), Niemirów, Sutno, Wajków, Mętna, Adamowo, Radziwiłówka, Moszczona Królewska, Osłowo, Maćkowicze i Kudelicze.
Młody, energiczny proboszcz przystąpił do budowy nowej plebanii. Po uzyskaniu pozwolenia na budowę, w sierpniu 1969 roku położono kamień węgielny i już po dwóch latach 21 września 1971 r. miało miejsce poświęcenie domu parafialnego. Sukcesywnie odnawiane były też ikony Matki Bożej i Apostołów w parafialnej cerkwi. W 1975 r. rozpoczęto budowę cmentarnego ogrodzenia. Prace nie były łatwe ze względu na dużą różnicę poziomów, ale zostały doprowadzone do końca. W 1982 r. rozpoczęto kapitalny remont cerkwi: prace obejmowały wymianę więźby dachowej, futryn okiennych, drzwi, instalacji elektrycznej, tynków zewnętrznych i wewnętrznych.
W 1984 r. została też wyremontowana kaplica na cmentarzu, gdzie dobudowano dzwonnicę. Dużą pomocą w tym czasie proboszczowi służyli: stróż parafii Mikołaj Adamiuk, starosta Józef Boguszewski, dyrygent Anna Michajłowna Michnowska.
W 1994 r. po długich poszukiwaniach ikonopisca przystąpiono do położenia fresków we wnętrzu świątyni. Ich wykonawcą był Aleksander Sokołow z Moskwy. Praca na mokrym tynku wymagała niebywałej wprawy i koncentracji. W tym samym roku 15 października odbyło się położenie kamienia węgielnego pod budowę kaplicy świętych Cyryla i Metodego w Maćkowiczach. W uroczystości wziął udział metropolita warszawski i całej Polski Bazyli. Drewnianą kaplicę stawiał Włodzimierz Sołomianko ze Stacji Siemiatycze, Jerzy Dacewicz krył dach i wykonał sufit, stolarkę okienną wykonał Wiaczesław Datczuk, a podłogę – Tadeusz Szymański z synami. Pierwszą Św. Liturgię odprawiono 24 maja 1997 r. w dniu patronów – świętych Cyryla i Metodego. 21 września 1999 r. na prestolnyj prazdnik w dzień Narodzenia Bogarodzicy duszpasterską wizytę w parafii złożył metropolita warszawski i całej Polski Sawa. Proboszcza o. Eugeniusza Niesteruka nagrodził wówczas mitrą.
Sukcesywnie w parafii prowadzone były prace, jak: założenie odgromienia cerkwi, szalowanie kaplicy od wewnątrz, usunięcie starych drzew przy cerkwi, ogrodzenie parafialnego domu wraz z parkingiem, docieplenie plebanii, pozłocenie ikonostasu w cerkwi, podświetlenie cerkwi, powiększenie cerkiewnego pogostu, ułożenie polbruku wokół cerkwi, wybudowanie parkanu i głównej bramy do cerkwi, postawienie krzyża na Górze Prowały i krzyży wokół Mielnika. W latach 2007/2008 cerkiew i kaplica zostały pokryte miedzianą blachą.
5 maja 2011 r. zmarł długoletni proboszcz parafii Mielnik i dziekan okręgu siemiatyckiego ks. prot. mgr Eugeniusz Niesteruk. W uroczystościach pogrzebowych wziął udział metropolita warszawski i całej Polski Sawa w asyście licznie zebranego duchowieństwa i rzeszy wiernych. Ks. Eugeniusz został pochowany na dojlidzkim cmentarzu, przy cerkwi św. Eliasza w Białymstoku. Dla upamiętnienia jego 45-letniej posługi w mielnickiej parafii, staraniem rodziny i parafian, od strony wejścia do cerkwi został postawiony pomnik.
W 40. dniu odbyło się żałobne nabożeństwo z udziałem Jego Eminencji metropolity Sawy, po którym ogłosił on, iż nowym proboszczem parafii został mianowany dotychczasowy wikariusz parafii Zmartwychwstania Pańskiego w Siemiatyczach ks. prot. mgr Mikołaj Mielniczuk. Po nominacji przystąpiono do odnowienia i remontu plebanii. Ponadto został przeprowadzony remont zewnętrznej elewacji kaplicy.
Mielnicka parafia posiada bogate tradycje, które były pielęgnowane przez wiele pokoleń: kolędowanie po wieczerzy wigilijnej, obchody pól (szczególnie uroczyście w Moszczonie Królewskiej z wejściem na Górę i Źródło Prowały), modlitwa przy pomniku zabitych przez Niemców mieszkańców Kudelicz, święcenie jordańskiej wody na rzece Bug, koncerty kolęd w Mielniku, Radziwiłówce i Moszczonie Królewskiej.
Od lipca 2011 r. stróżem cerkiewnym został Wsiewołod Jaroszuk z Mielnika, a chórem dyryguje Barbara Rusnak, absolwentka Wydziału Dyrygentury przy Akademii Duchownej w Sankt Petersburgu. Jesienią tego samego roku została zakupiona do cerkwi nowa grobnica (baldachim) i przywieziona z Łucka na Ukrainie. Pięknie komponuje się z wcześniej pozłoconym ikonostasem i czterema bocznymi kiotami.
Najważniejszymi wizytami arcypasterskimi w Mielniku w ostatnim czasie były: wizyta arcybiskup Aten i całej Grecji Chrystodulosa oraz metropolity Sawy i spotkanie z parafianami (2002), spotkanie Jego Eminencji metropolity Sawy z władzami samorządowymi Podlasia (2004), poświęcenie zbiornika na ropę w Adamowie przez biskupa bielskiego Grzegorza (2004), zjazd matuszek Diecezji Warszawsko-Bielskiej z udziałem Jego Eminencji metropolity Sawy (2006), wizytacja w szkole biskupa siemiatyckiego Jerzego (2007).
ks. prot. mgr Mikołaj Mielniczuk, fot. archiwum parafialne