Buchholz ist die erste urkundlich erwähnte Siedlung im Bereich der Pfarrei Herschwiesen. Bereits für das Jahr 1657 ist in Buchholz eine Filialkapelle zu Ehren der Heiligen St. Sebastian, St. Barbara und St. Katharina erwähnt; diese scheint im Dreißigjährigen Krieg (1618–1648) verbrannt zu sein. Im 18. Jahrhundert besaß der Ort Buchholz nachweislich wieder eine Kapelle (erbaut wohl 1738), die im Jahr 1846 erneut wiederhergestellt werden musste. Diese wurde mit der Zeit jedoch so baufällig, dass sie 1888 baupolizeilich geschlossen und im Jahr 1891 abgerissen wurde. Unmittelbar nach dem Abriss wurde jedoch mit der Planung eines neuen Kirchengebäudes begonnen und hierfür Spendengelder gesammelt.[Anm. 1]

Der noch heute erhaltene Bau der katholischen Kirche St. Sebastian neben der ehemaligen Schule am nördlichen Ortsrand von Buchholz wurde schließlich in den Jahren von der Grundsteinlegung am 23. Juni 1892 – der Rohbau der Kirche stand bereits im November selbigen Jahres – bis zu seiner kirchlichen Weihe am 20. Januar 1896 unter Federführung des Buchholzer Maurermeisters Philipp Weber errichtet; zuvor hatte der Bau ab Ende des Jahres 1892 bis 1895 mangels aufgrund von Missernten kaum noch eingehender Spenden zur Finanzierung des Projektes drei Jahre lang ruhen müssen. Die alte Dorfkirche St. Sebastian besteht aus einem dreiachsigen Schiff mit einem neuromanischen Westturm; im Winkel zwischen Turm und Schiff lässt sich eine Freitreppe aus Basaltblockstufen entdecken. Unverputzter, roter Backstein ist das Baumaterial der Außenwände, die durch Lisenen und Rundbogenfriese gegliedert werden. Wie das alte Schulhaus in Buchholz, so besteht auch der Sockel der katholischen Kirche aus Bruchsteinen. Der Altar der Kirche stammte noch aus dem Vorgängerbau des 18. Jahrhunderts; 1897 war zudem eine Glocke für den Kirchenbau beschafft worden.[Anm. 2]

Während des Zweiten Weltkrieges wurde das Kirchengebäude zu Beginn des Jahres 1945 teilweise beschädigt, 1949 aber wieder instandgesetzt. Aufgrund der wachsenden Einwohner:innenzahl von Buchholz ab den 1950er Jahren stieg auch die Anzahl der Katholiken und Kirchgänger im Ort an. Da die bisherige Pfarrkirche nur 110 Sitzplätze fasste, wurde auf Betreiben eines Kirchenbauvereins im Jahr 1966 zum Zwecke eines Kirchenneubaues ein Grundstück im östlichen Neubaugebiet Buchholz-Mitte erworben und 1967 ein Architektenwettbewerb ausgeschrieben. Seit dem Jahr 1969 ist Buchholz zudem Sitz der selbstständigen katholischen Kirchengemeinde St. Sebastian. 1974 erfolgte schließlich die Grundsteinlegung für das neue Pfarrzentrum, welches unter einem beide Gebäude verbindenden Dach zukünftig auch das 1975 eingeweihte Zentrum der evangelischen Kirchengemeinde (deren Mitglieder durch den Zuzug von Neubürgern ab den 1960ern angewachsen war) beheimatete, sowie das neue Kirchengebäude mit etwa 400 Sitzplätzen. Im Jahr 1979 wurde der architektonisch ganz im Sinne der liturgischen Erneuerung durch das Zweite Vatikanische Konzil (1962–1965) gehaltene Bau, dessen Kosten sich insgesamt auf etwa 1.258.000 Mark belaufen hatten, feierlich eingeweiht. Die Bildwerke und Innenausstattung der alten, nun profanierten Pfarrkirche von 1892 wurden indes in den Neubau überführt – in ersterer verblieben ist lediglich der frühere Altar. Ein geplanter Abriss des alten Kirchenbaus konnte im Jahr 1978 verhindert werden, indem die ehemalige Kapelle unter Denkmalschutz gestellt wurde; seit 1990 beheimatet der Bau ein Architekturbüro.[Anm. 3]