Pirmoji katalikų bažnyčia Riebiniuose pastatyta 1771 m. Tai buvo vienbokštis medinis pastatas, apkaltas lentomis. Pirmosios bažnyčios statybą fundavo dvarininkas Veisenhofas. Pastačius mūrinę bažnyčią – senoji buvo nugriauta kaip nebetinkama naudoti.
Dabartinė bažnyčia ant Feimanių upės kranto statyta Dominyko Andriekaus (Andrekaus) klebonavimo laikotarpiu (parapijos klebonu buvo paskirtas 1894 m. rugpjūčio 1 d.). Naujajai bažnyčiai panaudoti Nydermuižos bažnyčios (Nīdermuižas baznīca) statybos planai. Darbams vadovavęs tas pats meistras, kuris statęs ir Nydermuižos bažnyčią. Riebinių bažnyčios statybų metu pasitaikė ir incidentų – buvo padegta klebonija, sudegė ąžuolinė mediena, jau pagamintos durys, langai. Kai 1908 vasario 15 d. klebonas D. Andriekus mirė, bažnyčios įrengimo darbus tęsė ir ją 1909 m. konsekravo naujai paskirtas klebonas Antonas [Antanas?] Racevičius.
Dominykas Andriekus gimė 1827 m. liepą (pakrikštytas liepos 30 d.) Kivylių kaime, Aleksandrijos valsčiuje (Skuodo r.), tuometinėje Telšių apskrityje. Baigė Telšių apskrities mokyklą, 1851–1855 m. mokėsi Minsko-Mogioliovo dvasinėje seminarijoje. Kunigas Dominykas Andriekus labai nusipelnė Latgalos kraštui, jos žmonių švietimui ir tapatybės žadinimui. Pagarsėjo, kai 1875 m. vasarą suorganizavo latgaliečių valstiečių vaikų „desantą“ į Jelgavos (Mintaujos) mokyklas: katalikų bažnyčios mokyklą, apskrities mokyklą (vėliau tapusią realine mokykla), rūpinosi jų apgyvendinimu. Tarp tuomet į Jelgavą palydėtų mokinių buvęs ir Francis Trasunas – žymus latvių katalikų kunigas, kultūros veikėjas, latvių tautos vienytojas, nepriklausomybės puoselėtojas ir Latvijos Respublikos parlamento (Saeimos) deputatas. Latvių spaudoje D. Andriekus buvo vadinamas „vyru, nusipelniusiu Latgalos atgimimui“, „latgaliečių švietimo skatintoju“ ir panašiai.
