Pirmoji Tirkšlių mokykla įkurta dar XVIII a. miestelio centre, Važinskių dvaro sodybos vietoje.
1750 m. Tirkšliuose įsteigta parapinė mokykla. Parapines mokyklas daugiausia lankė neprivilegijuotų luomų vaikai, kurie mokėsi tikybos, giedoti, skaityti, kai kuriose rašyti, skaičiuoti, lotynų ir kai kur, daugiausia Žemaitijoje, lietuviškai.
1804 m. mokykloje mokėsi tik 20 berniukų, o 1815 m. jau 40 berniukų ir 15 mergaičių.
1867m. spaudos draudimo metais, valdant carinei Rusijai, buvo įsteigta valdinė pradžios mokykla, išsilaikiusi apie 50 metų. 1909 m. šioje mokykloje dirbo du mokytojai, iš kurių vienas buvo lietuvis. 1918 m. to meto ,,Lietuvos Aido“ numeryje rašoma, kad mokykla neveikė, nes po karo, Lietuvai atkūrus valstybę, visa inteligentija išsikraustė. Tačiau jau 1919 m. Juciaus namuose įsteigta lietuviška pradžios mokykla, kurią pradėjo lankyti 150 vaikų.
1920 m. Tirkšlių pradinė mokykla išleido pirmąją laidą.
Po Antrojo pasaulinio karo 1945 m. mokykla reformuota į progimnaziją, o 1950 m. ji tapo septynmete.
1954 m. mokykla pervadinta Juozo Garelio vidurine mokykla (pavadinimo atsisakyta 1990 m.), o 1958 m. išleista pirmoji 17 moksleivių abiturientų laida.
2005 m. prie Tirkšlių vidurinės mokyklos prijungiama Pievėnų pradinė mokykla; kaip skyrius veikė iki 2007 m.
Nuo 2009 m. iki 2013 m., mokyklai priklausė Šerkšnėnų pradinio ugdymo skyrius.
2013 m. Tirkšlių vidurinė išleido paskutinę 56-ąją abiturientų laidą ir buvo reformuota į pagrindinę mokyklą, kuriai suteiktas Juozo Vitkaus-Kazimieraičio vardas.
2019 m. prie mokyklos prijungta Balėnų pradinė mokykla, o 2021 m. prijungtas Žemalės pradinio ugdymo skyrius.
Tirkšlių pagrindinė mokykla nuo 2023-09-01 keičia mokyklos struktūrą ir tampa progimnazija, kuri yra orientuota į mokinių ugdymą ir ruošimą mokytis rajono gimnazijose.
Keitėsi abiturientų laidos, direktoriai, mokytojai, mokinių skaičius. Direktoriai:
- 1954–1959 m. – Vincas Liauba
- 1959–1963 m. – Adomas Šoblinskas
- 1963–1965 m. – Voldemaras Strumskis
- 1965–1967 m. – Kazys Gražys
- 1967–1982 m. – Kazys Gudonis
- 1982–1985 m. – Stasys Šiurkus
- 1985–1998 m. – Stasys Inta
- 1998–2004 m. – Apolinaras Stonkus
- 2004–2021 m. – Marius Vilimas
- 2021–dabar – Dovilė Budreckienė