W dokumentach historycznych, pierwszą wzmiankę o Brzostku znajdujemy w dokumentach legata Idziego z lat 1125-1126, jako przynależącym do klasztoru Benedyktynów z Tyńca z siedzibą w Kleciach. W Kleciach był kościół p.w. św. Leonarda Opata z jego obrazem w wielkim ołtarzu. Obraz ten ściągał liczne pielgrzymki wiernych, także ościennych krajów. Pielgrzymi otrzymywali tu różne łaski, o czym wspomina ks. Jan Długosz. Oprócz kościoła w Kleciach był także kościół w Brzostku. Wzmianka o nim pochodzi z 1367 r. Za czasów ks. Jana Długosza obydwa kościoły były pod zarządem proboszcza w Brzostku a kościół w Kleciach stał się filialnym.
W wyniku rozbiorów Brzostek znalazł się w granicach Austrii, a parafia włączona została do Diecezji Przemyskiej, dotąd należała do diecezji Krakowskiej. W tym też czasie skasowano klasztor benedyktynów w Kleciach, a kościół w 1829 r. przeniesiono do Sieklówki (w 1992 r. spłonął). Na miejscu przeniesionego kościoła wybudowano w 1890 r. neogotycką kaplicę. W Brzostku zaś na miejscu starego kościoła wybudowano nowy kościół, w stylu klasycystycznym, p.w. Podwyższenia Krzyża Świętego, konsekrowany w 1826 r. Z kościoła w Kleciach, przeniesiono do nowego kościoła w Brzostku renesansowy Ołtarz św. Leonarda i chrzcielnicę.
Obecny kościół parafialny, podczas drugiej wojny światowej, został poważnie uszkodzony. Pocisk zniszczył wieżę, a powstały pożar strawił dach kościoła, organy i wyposażenie. Ołtarze jednak ocalały. Po wojnie kościół odbudowano i odrestaurowano. Pod koniec XX wieku kościół ponownie odrestaurowano, dobudowano boczne nawy, położono nową polichromię, przeprowadzono renowację Ołtarza św. Leonarda.
W latach 1995-97 w Bukowej wybudowano kościół filialny p.w. Przemienienia Pańskiego. Bp Kazimierz Górny, Ordynariusz Rzeszowski, dokonał jego poświecenia w dniu 06.08.1997 r.
Kościół parafialny
(lata międzywojenne)
Kościół parafialny
(wygląd obecny)
Ołtarz św. Leonarda
Ołtarz
Ołtarz Matki Bożej
Kościół filialny w Bukowej