Pierwsze wzmianki o miejscu Dubeninki, dawna nazwa Dubeningen, pochodzą z 1615 roku. Rok ten uważany jest też jako założenie tej wsi czynszowej przez Krzysztofa Gordeckiego. Natomiast pierwsza parafia powstała niewiele później, bo już w 1620 r. i wtedy też wybudowano pierwszy kościół. W tym miejscu można nadmienić że obecna świątynia jest czwartą z kolei a do 1945 r. była to parafia ewangelicka.

Po wybudowaniu pierwszego kościoła, następny powstał w 1683 r. i był to obiekt drewniany. Trzeci powstał w 1743 r. tym razem z kamienia, ale nadal posiadał drewniana wieżę, którą jednak rozebrano w 1812 r. Kilka lat późnie,j bo w 1818 r. nastąpiły bardzo poważne zniszczenia z powodu katastrofalnej wręcz wichury. Było to bezpośrednim powodem budowy ponownie nowej świątyni (tym razem po raz czwarty), co nastąpiło w roku 1822.

W późniejszych latach miało miejsce jeszcze kilka remontów i przebudowań. Najbardziej znamienny w 1879 r. kiedy to postawiono nową wieżę na fundamentach poprzedniej. Wygląd obecny pochodzi z roku 1903. Od tamtego okresu nie nastąpiły żadne przebudowania.

Po II wojnie światowej miejsce ludności protestanckiej zajęła napływowa ludność katolicka, głównie z terenów Suwalszczyzny. W 1946 r. dokonano poświęcenia kościoła już jako świątyni katolickiej powierzonej opiece św. Andrzejowi Boboli oraz św. Apostołom Piotrowi i Pawłowi. Wówczas jeszcze, mimo że kościół posiadał filię w Żytkiejmach, nie był samodzielną placówką. Opiekę duszpasterską nad wiernymi sprawowali tu duchowni dojeżdżający z parafii Przerośl.

Dubeninki jako samodzielna parafia została kanonicznie erygowana w 1952 r. a szafarzem ceremonii był, dzisiaj niemal legendarny, ks. biskup Tomasz Wilczyński.