Do 1809 r. Brzostek był własnością opactwa tynieckiego i był zamieszkany wyłącznie przez osoby wyznania katolickiego. Pierwsi Żydzi zaczęli osiedlać się w Brzostku dopiero w 1816 r. W roku 1845 została utworzona gmina żydowska zrzeszająca okoliczne miejscowości. Kirkut powstał prawdopodobnie w połowie wieku XIX. W roku 1880 Żydzi stanowili już ok. 30 % mieszkańców miasteczka.
Do 1939 r. cmentarz o powierzchni 0,8 ha otoczony był drewnianym płotem a przed bramą istniał dom pogrzebowy. W czasie wojny cmentarz był miejscem masowych egzekucji ludności żydowskiej. Po wojnie w Brzostku nie pozostał żaden przedstawiciel przedwojennej społeczności żydowskiej. Zniszczony podczas wojny cmentarz w kolejnych powojennych latach ulegał dalszej dewastacji a nagrobki były wykorzystywane jako materiał budowlany m.in. w pracach melioracyjnych. Część cmentarza została zajęta przez Spółdzielnię Kółek Rolniczych.
Pierwsze postulaty dotyczące upamiętnienia przedwojennych mieszkańców wyznania mojżeszowego pojawiły się dopiero w latach 80-tych. W latach 90-tych na miejscu dawnego kirkutu postawiono pomnik. Na początku XXI w. cmentarz był stopniowo odnawiany i 14 czerwca 2009 r. został ponownie konsekrowany. Zaangażowanie miejscowej społeczności, w tym księdza z miejscowej parafii, burmistrza oraz Muzeum Okręgowego w Tarnowie doprowadziło do odnalezienia kilkudziesięciu macew, które odrestaurowane zostały ustawione na terenie kirkutu. Historię odtworzenia cmentarza opowiada film dokumentalny „Brzostek: historia pewnego powrotu”