Parafię w Majewie ustanowił mocą dekretu erekcyjnego z 12 grudnia 1919 r. bp Jerzy Matulewicz. Jej terytorium wydzielono z parafii Sokolany, Sidra i Janów. Pierwszym proboszczem został ks. Adam Baranowski.
Projekty wzniesienia kościoła na górze w Majewie snuł już od roku 1907 ks. Tadeusz Makarewicz, proboszcz parafii Sokolany. Ideę tę mieszkańcy Majewa podjęli i natychmiast rozpoczęli starania o pozwolenie na budowę świątyni. Uzyskali je w tempie, jak na owe czasy, błyskawicznym. Projekt kościoła z kamienia polnego, w stylu neogotyku angielskiego, wykonał arch. Marian Behr, właściciel majątku Lisie Nory, nazwanych później Pańską Jałówką. Prace budowlane rozpoczęto w 1910 r., jednakże do wybuchu I wojny światowej murów wykończyć nie zdążono. Nastąpiła przerwa. Dopiero zaprzestanie działań wojennych na tych ziemiach, pozwoliło na oddelegowanie do Majewa na jesieni 1919 r. osobnego duchownego. Doprowadziło to do powołania parafii i pozwoliło na wznowienia prac budowlanych. W latach 1924-26 budowa osiągnęła już taką fazę, że kościół można było poświęcić, czego też w grudniu 1926 r. dopełniono. W świątyni w Majewie zaczęto sprawować nabożeństwa. Dalsze prace wykończeniowe i wyposażenie kościoła były już dziełem ks. proboszcza Antoniego Czechowicza.
On też w roku 1930 sprowadził do świątyni kopię obrazu Matki Boskiej Częstochowskiej, który wkrótce zaczął być otaczany kultem jako słynący łaskami, ściągając jednocześnie rzesze wiernych z sąsiednich parafii. Stąd też wkrótce pierwotne wezwanie kościoła i parafii (Matki Boskiej i św. Kazimierza) doprecyzowano i zmieniono na Matki Boskiej Częstochowskiej i św. Kazimierza. Polichromię w świątyni majewskiej wykonał przed kilkoma laty białostocki artysta-malarz Marek Karp.