Bodendorf hatte seit dem Jahr 1282 eine eigene Pfarrei. Eine Vorgängerkirche der heutigen Pfarrkirche St. Sebastianus muss spätestens seitdem bestanden haben, wurde aber im Dreißigjährigen Krieg (1608-1648) zerstört. 1647 errichtete die Gemeinde einen Nachfolgebau, der Ende des 19. Jahrhunderts abgerissen werden musste, da er zu klein geworden war. Der Ahrweiler Kreisbaumeister Hermann Cuno (1831-1896) wurde damit beauftragt, in Bodendorf eine Kirche im neugotischen Stil zu erbauen. Die Weihe des dreischiffigen Gotteshauses mit dem weithin sichtbaren, spitzen Turm erfolgte 1882. Doch schon in den 50er Jahren des letzten Jahrhunderts wurde der Kirchenraum wieder zu klein für die stark anwachsende Gemeinde und musste erweitert werden. Man entschied sich dafür, ein Seitenschiff zu opfern und einen Neubau anzufügen, so dass im Innenraum der Kirche heute Neues und Altes einen interessanten Kontrast bildet.