Parafia w Majewie pod wezwaniem Matki Boskiej Częstochowskiej i Św. Kazimierza jest stosunkowo młodą. Inicjatorem rozpoczęcia budowy kościoła w 1907 r był ks. Tadeusz Makarewicz, proboszcz parafii w Sokolanach, do której teren majewski należał. Nowo utworzona parafia objęła jeszcze miejscowości z 3 parafii: sokolańskiej, sidrzańskiej i janowskiej.

W 1906 roku Komitet Organizacyjny pod przewodnictwem właściciela majątku w Jałówce Mariana Behra i Wiktora Kochanowskiego, rozpoczął prace przy wznoszeniu świątyni. Kamień węgielny pod budowę świątyni w roku 1908 poświęcił ks. Stanisław Szyroki, pełniący obowiązki dziekana sokólskiego

Z chwilą erygowania parafia otrzymała pierwszego proboszcza. Został nim ks. Adam Baranowski. Urząd proboszcza, pełnił on tu już prawdopodobnie we wrześniu, a na pewno w listopadzie, a więc jeszcze przed oficjalną erekcją parafii. Obecność nowego kapłana potwierdza księga metryk pogrzebowych, gdzie ks. Baranowski zanotował, iż dnia 13 listopada 1919 roku pochował jako pierwszą Mariannę Bielawską. Pierwsza wojna światowa wstrzymała prace przy budowie świątyni. Do tego czasu wzniesiono mury do wysokości okien.

Dopiero po odzyskaniu niepodległości, już w wolnej Polsce parafię erygował 12 grudnia 1919 r. biskup wileński Jerzy Matulewicz. Parafii i kościołowi nadano wezwanie Opieki Matki Boskiej i św. Kazimierza.

Świątynia została wzniesiona na wzgórzu w całości z kamienia polnego. Przy pracach budowlanych brała udział cała parafia. Nowo utworzona parafia liczyła około 1200 wiernych.

Nowy proboszcz stanął przed problemem, gdzie odprawiać Mszę św. i sprawować sakramenty. W tym celu zbudował w 1920 r. Drewnianą kaplicę na cmentarzu grzebalnym. Nie służyła ona zbyt długo, gdyż w 1921r. w skutek zaprószenia ognia zupełnie spłonęła. Ks. Baranowski pracował w tej parafii trzy lata. W czerwcu 1922 r. władze duchowne zmieniły proboszcza. Został nim ks. Edward Cerran, który pracował tylko przez rok.

We wrześniu 1923 r. nominację na proboszcza otrzymał ksiądz Kasper Wołodkiewicz. Właśnie dzięki staraniom tego kapłana prace przy budowie zaczęły się posuwać.

W roku 1927 wykończona świątynia zaczęła pełnić funkcję kościoła parafialnego. Również za czasów tego kapłana został wybudowany dom pielgrzyma, zwany ludowym. Ksiądz Wołodkiewicz w 1929 roku, opuścił parafię i wyjechał w okolice Wilna. Parafia Majewo została bez opieki duszpasterskiej na przeszło pół roku.

Taki stan trwał do wiosny 1930 r. w którym nominację na proboszcza otrzymał ksiądz Antoni Czechowicz.

Według zamierzeń nowego proboszcza, w Majewie miała stanąć "mała Częstochowa". Za jego czasów dokończono tynkowania wewnętrznych ścian i pomalowano wnętrze kościoła. W 1930 r. ks. Antoni z delegacją parafian, prawdopodobnie w miesiącu wrześniu, przywiózł z Częstochowy kopię cudownego obrazu Matki Boskiej Częstochowskiej, wykonaną w firmie "Ryngraf Podjasnogórski", pędzla artysty Rutkowskiego. Obraz ten ufundowali Wiktor i Petronela Deputatowie z Kładziewa. Na Jasnej Górze było uroczyste przekazanie obrazu przez jednego z ojców Paulinów delegatom z parafii na czele z ks. Czechowiczem. Obraz przywieziono pociągiem do stacji kolejowej w Sokółce. Tu już czekała procesja, która przybyła z Majewa i piechotą ze śpiewem na ustach udała się z obrazem do świątyni majewskiej, gdzie umieszczono obraz Matki Bożej w głównym ołtarzu. Ks. Antoni Czechowicz sprowadził także piękną figurę Zbawiciela Ukrzyżowanego, naturalnej wielkości, wykonaną w drzewie przez utalentowanego rzeźbiarza z Krakowa, według kopii na wzór figury z Jasnej Góry.

W tym czasie wiele innych utensyliów zostało zakupionych na wyposażenie kościoła w Majewie. (Wykonane z brązu w stylu gotyckim, wewnątrz wyłożone złoconą blachą. Na drzwiczkach posrebrzany ornament kielich z hostią stojący na chmurce. Na tabernakulum ustawiony pięknie wykonany krzyż również z brązu, a przed obrazem 28 lichtarzy z licznie przymocowanymi wieżyczkami, a wszystko to w tym samym stylu gotyckim. Ks. Czechowicz kupił też do świątyni trzy żyrandole wykonane z brązu, w stylu gotyckim, ozdobione kryształkami szkła. Oraz liczne szaty i paramenty liturgiczne.)

Jego wspaniałe, płomienne kazania rozpalały serca wiernych. Z wielu stron poczęli ciągnąć do Majewa pielgrzymi. Ks. Antoni Czechowicz wyróżniał się wielką gorliwością w służbie Bożej. Nabożeństwa które organizował podobały się wiernym, tym bardziej, że proboszcz przeplatał modlitwy własnym śpiewem.

Nabożeństwo do Matki Boskiej zapoczątkował ks. Czechowicz w 1930 r. W przekonaniu ludzi obraz Matki Boskiej Częstochowskiej w Majewie jest wsławiony licznymi łaskami. Widocznym znakiem orędownictwa u Boga, stały się wota zawieszane wokół obrazu, przez tych, którzy z wiarą i modlitwą doznawali pociechy i pomocy, a może i cudu.

Przed cudowny wizerunek przychodzono z najróżniejszymi prośbami i najtrudniejszymi sprawami. W 1935 r. zostaje proboszczem ks. Jan Malinowski, który w Majewie pracuje przez 10 lat. Za jego czasów zostaje ukończona budowa wieży i całego kościoła.

W 1938 r. ks. proboszcz Jan Malinowski opisał w gazecie "Tygodnik Katolicki Nasz Przyjaciel" fakt uzdrowienia w Majewie ośmioletniego chłopca. Dnia 8 stycznia 1938 roku Aleksander Samojłowicz z żoną przybył ze wsi Marchelówka parafii Janów do cudownego obrazu Matki Boskiej Częstochowskiej w Majewie z prośbą o zdrowie dla ich syna Stanisława liczącego 8 lat. Chłopiec był ciężko chory na ropienie płuc. Stan jego był beznadziejny, jak twierdził lekarz janowski dr D. Berger. Intensywne leczenie było bezskuteczne. Rodzice zamówili Mszę św. o zdrowie chorego. Po odbyciu spowiedzi i przyjęciu Komunii świętej gorąco modlili się przed obrazem Matki Bożej o zdrowie dziecka. Po powrocie do domu opowiedzieli synowi o tym, że się modlili za niego w Majewie. Chłopiec był tym bardzo wzruszony, przy pomocy ojca usiadł na łóżku, poprosił o posiłek, którego przedtem prawie nie przyjmował, a za pięć dni całkowicie wyzdrowiał i do dnia dzisiejszego cieszy się jak najlepszym zdrowiem.

Także inne uzdrowienia miały miejsce przed wizerunkiem Matki Bożej. Wspomina Monika Lisowska mówiąc o sobie, że "jako młoda 20 letnia dziewczyna zaczęła tracić wzrok. Chyba również za ks. Malinowskiego, leżała krzyżem przed Cudownym wizerunkiem w czasie Mszy św. i prosiła Boga o zdrowie oczu. Modlitwa była naprawdę skuteczna, a prośba wysłuchana, gdyż dziś mając 90 lat może czytać bez okularów. Po tych modlitwach obiecała Matce Bożej, że codziennie będzie odmawiała różaniec.

Kościół został otoczony monumentalnym murem z kamienia polnego, na wzór Wałów Częstochowskich. Na murze miały stanąć stacje drogi krzyżowej, w których figury miały mieć naturalną wielkość. Z powodów finansowych, ks. proboszcz ograniczył się do niewielkich kapliczek drogi krzyżowej z płaskorzeźbami odlanymi w betonie. Całe Wały okalające świątynię zostały ukończone dopiero w roku 1970.

Kolejnym proboszczem został mianowany ks. Izydor Pietrasz, który objął parafię w jesieni 1945 r. Doprowadził on świątynię do stanu użyteczności po działaniach wojennych.

Następnym proboszczem parafii był od 1947 r. ks. Mieczysław Skrobot.

Pracował on w parafii Majewo 40 lat do 1987 r. Za czasów jego proboszczowania został ukończony mur okalający kościół z kapliczkami drogi krzyżowej, zbudowano nowy ołtarz Serca Pana Jezusa w roku 1957 , oraz w roku 1986 zmieniono główny ołtarz na nowy. Jest pięknie rzeźbiony z drzewa dębowego, pomalowany lakierem bezbarwnym. Kościół został zelektryfikowany, zradiofonizowany, zmieniono posadzkę, jak również zmieniono pokrycie dachu.

Kolejnym proboszczem w 1987 r. został ks. Józef Bielski, pracował on do 1990 r. Staraniem tego proboszcza została wybudowana nowa plebania.

Po nim w 1990 r. urząd proboszcza obejmuje ks. Adam Sokołowski, który pracuje tu do dnia dzisiejszego.

Główne uroczystości kościoła w Majewie powiązane są ściśle z tytułem parafii. I tak, 4 marca - odpust św. Kazimierza, w ostatnią niedzielę sierpnia - odpust Matki Boskiej Częstochowskiej poprzedzony 40-godzinnym nabożeństwem, zakończony uroczystą sumą z procesją o godz. 12.15.

Dekretem Ks. Arcybiskupa Stanisława Szymeckiego kościół w Majewie został zaliczony do grona świątyń diecezjalnych jako miejsce uzyskania Jubileuszowego odpustu.