U davna vremena prije Austro-ugarske okupacije, Priboj nije imao svoju crkvu, već su njegovi stanovnici i oni iz obližnjih sela odlazili na bogosluženja u Mačkovac i manastir Tavnu. Ali pošto se na putu do manastira Tavana nalazilo tursko naselje u Teočaku, Turci su činili zulum narodu prilikom njihovog prolaska, što je narodu dojadilo. Početkom 19. vijeka iz Čaklovice u Priboj se doselio neki Veselin sa sinom Gavrom, koji je nešto znao čitati i pisati, zamole seljani Veselina da pošalje Gavru u manastir da se malo douči i da im bude pop.

  I zaista nakon izvjesnog vremena vrati se Gavro iz manastira i zvornički mitropolit ga rukopoloži za pribojskog sveštenika.
Tako je Gavro Veselinović bio prvi poznati pribojski paroh i posle njega imao je ovaj kraj stalno po jednog, dva ili više sveštenika u Priboju. Gavro Veselinović je umro 1884. godine i sahranjen je na Petrovića groblju u Priboju.

  Prva pribojska crkva zvana „Ćelija“ nalazila se u Gornjem Priboju. Zbog toga se to mjesto i danas naziva „Popovići“. Na tome mjestu danas žive Gavrići i Jovići potomci i srodnici bivših pribojskih sveštenika. U „Ćeliji“, koja nije imala zvona, jer se u tursko vrijeme zvonjenje strogo zabranjivalo, vršene su samo jutarnje i večernje molitve a svi drugi obredi su se obavljali kao i prije u Mačkovcu i manastiru Tavni. Sve je to otežavalo vjerski i bogoslužbeni život, pa su Pribojčani preduzimali korake za gradnju crkve u selu, ali nisu nikada dobijali dozvolu od turskih vlasti.

   Tek u decenijama pred austrijsku okupaciju Pribojčani i njihov paroh, protojerej Savo Gavrić, sin popa Gavre, dobijaju ferman od sultana u kome se odobrava u Priboju gradnja kapele. Odmah posle toga seljaci sagradiše malu kapelu, na mjestu gdje se nalazi današnja crkva. To je bila omanja drvena zgrada pokrivena daskom kao što je bila i „Ćelija“ urađena. Pošto je stara crkva bila od drveta i slabo građena te se ubrzo srušila. Kada se stara crkva srušila podignuta je kapela niže današnje stare škole u kojoj je svršavano bogosluženje do osvećenja nove crkve.

Mjesto za gradnju kapele je izabrano pošto se tu nalazilo “molitvište“, mjesto gdje se narod, u nedostatku crkve, okupljao sa sveštenikom na molitvu.

   To mjesto bilo je u vasništvu /u „čitluku“/ nekog Salihage /Salke/ Mujagića iz Teočaka. Kada je došla austrougarska okupacija Bosne i Hercegovine, riješiše mještani Priboja i okolnih sela da grade zidanu crkvu. Pošto su izabrali ovo mjesto zvano „molitvšte“, ode njih nekoliko viđenijih domaćina u Teočak kod Salihage Mujagića, kako je zapisao Risto Lukić, „i zamole ga da im proda to zemljište“. Kada su ga to upitali, odgovorio im je: „Ne mogu vam prodati“ i upita: „A šta će vam?“, na to oni odgovoriše: „Hoćemo da pravimo crkvu“. On malo poćuta, pa rekne: „Ako hoćete za crkvu , neću da prodam, nego ću da vam poklonim“. A oni: „Mi nećemo na poklon, nego hoćemo da platimo“. On je opet malo poćutao pa reče: “Pa eto, ako hoćete da platite, vi napravite meni kuću na mojoj zemlji zvanoj Karaula“.

Na to su oni rado s voljom pristali i naprave mu kuću na Karauli, a on njima prevede gruntovno isto zemljište na kome postoji danas crkva, a to jest sve do Janje vodenog korita i do puta iznad kuće popove.

Pošto su Pribojčani kupili zemljište za gradnju crkve, koje se u ugovoru o kupovini pojašnajva sa sledećim granicama; „Od istoka voda Janja, od zapada Vučkova košara, od juga voda Janja, a od sjevera prodavac i put.

Poslije rušenja stare crkve, parohijani zajedno sa protom Savom Gavrićem odlučiše da grade veliku crkvu, zidanu od kamena. U crkvenu opštinu pribojsku ulazila su pored Priboja još i sela: Tobut, Rastošnica, Rožanj, Brijest, Podgora i Lipovice. Gradnja crkve je trajala dvije godine a završena je i osvećena na Arlijevdan 1889. godine. Narod majevički je pokazao dobru volju te je pomogao gradnju crkve svojom pomoći i dobrovoljnim prilozima, a među njima je bilo  i dvadeset darodavaca od po 10 dukata, zvanih „desetari“ čija su imena upisana u povelju koja je uzidana u temelje današnje crkve. U izvorima koje posjeduje crkva spominju se četiri poznata “desetara“: Radovan Stanojević, Radovan Gajić i Prekan Radovanović iz Priboja i Rado Tomić iz Lipovica. Ostaloj šesnaestorici se ne znaju imena, ali zna ih Onaj u čiju čast i slavu su oni svoje dukate dali.

Za poređenje o kolikoj se vrijednosti radi koju je svaki od „desetara“ priložio može se navesti i to da je crkvena opština u to vrijeme kupila oranicu zvanu Polje (danas se običava da kaže: Crkveno polje) za 30 dukata, u Tobutu pored puta Priboj- Lopare, površine 10 dunuma .
Ova oranica „Polje“ nalazila se uz istoimenu parcelu, koju su prije ove kupovine, poklonili crkvi pribojskoj Stevo i Spasenija Đokić iz Tobuta.

  Iz ove pribojske porodice potekli su u dugom nizu godina, više sveštenika koji su služili u pribojskoj parohiji.
Tešo Jovanović, rođen je u Priboju 1843. godine. Pismenost je učio u Mačkovcu i manastiru Tavni, gdje se pripremao za svešteničku službu. Služio je u Priboju a opsluživao sela Tobut i Maleševce. Umro je 1895.godine i sahranjen u groblju kod crkve pribojske.
Jovo Jovanović sin sveštenika Teše, rođen u Priboju 1874. godine. Po svršenoj bogosloviji i rukopoloženju (1895) nasledio je oca na parohiji, a 1902. posle reorganizacije pripada mu pribojska parohija.
On je u Prvom svjetskom ratu, kao taoc, bio zatvoren u žandarmerijskoj stanici u Loparama, odakle je povremeno pod stražom puštan da obavi poneki crkveni obred. Osim svešteničke dužnosti posebno se isticao u radu na razvijanju nacionalne svijesti srpskog naroda na Majevici, zajedno sa učiteljom Veljkom Čubrilovićem. Umro je 1919. godine i sahranjen na groblju crkve pribojske.

  Ðorđe Jovanović, sin pribojskog sveštenika Jove, rođen je u Priboju 1909. godine. Nakon svršene bogoslovije 1933. postavljen je za paroha u Skugriću, a 1936. godine bio premješten u Priboj i postavljen za paroha rastošničkog. U toku Drugog svjetskog rata proveo je jedno vrijeme u izgnanstvu u Srbiji a zatim odveden u Njemačku , gdje je u logorima smrti Dahau i Mathauzenu, stradao i mučen. Preživio je strahote ovih logora ali narušenog zdravlja se vraća u rodni kraj. Služio je u Priboji sve do 1968. godine kada je zbog zdravstvenih razloga morao da ode u penziju. Umro je 1984. godine i sahranjen u Tuzli.

  Rođen je u Snagovu kod Zvornika 1946. godine. Po svršenoj bogosloviji rukopoložen je 1968.godine i postavljen za paroha pribojskog, Njegov dolazak u pribojsku parohiju predstavlja pravu prekretnicu u poratnom životu ove crkvene opštine. Mlad sveštenik, pun snage i elana, došao je na ovu elitnu seosku parohiju u vrijeme kada je naš seoski narod ekonomski ojačao, kada su materijalne ratne rane zacijelile i otpočeo nov način života i brzog napretka. Stvorila se situacija kao kada se svjež kvasac stavi u dobro brašno. Išlo se iz uspijeha u uspijeh. Jedan posao se završavao a novi se već predviđao i počinjao. Crkva je prekrivena bakrom, podignut je novi parohijski dom, kupljena su dva nova zvona, crkva je generalno opravljena, ograđena željeznom ogradom, podignuta zgrada za prodaju svijeća. U njego vrijeme sagrađena je 1972. godine nova crkva u Rastošnici, koja je do tada bila u sastavu pribojske crkvene opštine. Otac Stevan Vlačić premješten je 1982. godine za Tuzlu a sledeće godine za Beograd, gdje i sada službuje kao starješina hrama Svetog Save na Vračaru.
  Svi parohijani se rado sjećaju i pominju svoga sveštenika koga su običavali da zovu „otac Stevo“ iako mu je kršteno ime Stevan. Mnogi i danas, kada dođu u prijestoni grad naše matice, rado svrate na Vračar da posjete svog dugogodišnjeg duhovnog oca Stevana Vlačića.