Parafia w Zawadzie powstała prawdopodobnie w XII wieku. Pierwszy kościół powstał prawdopodobnie na miejscu pogańskiej gontyny. W 1400 roku parafia została zlikwidowana na rzecz nabierającego coraz większego znaczenia Tarnowa. Pierwsze wzmianki na temat kościoła w Zawadzie pochodzą z dokumentu z 1326 r.
Obecny, drewniany kościół został wzniesiony prawdopodobnie w wieku XV w stylu gotyckim i jest najstarszym zachowanym kościołem w okolicy Tarnowa. Przed 1665 rokiem został gruntownie przebudowany, m. in. została podwyższona wieża oraz wymieniony dach. W XVIII dobudowane zostały soboty. W kolejnych latach kościół przeszedł kilka gruntownych remontów. W roku 1980 parafia został przywrócona.
Budynek świątyni ma konstrukcję zrębową, jednonawową z zamkniętym trójbocznie prezbiterium. Otoczony jest zamkniętymi szalowaniami sobotami. Ściany oraz dach nawy i wieży obite są gontem. Wewnątrz zachowało się bogate zabytkowe wyposażenie, w tym gotyckie portale na wejściach do nawy (XV w.), belka tęczowa z krucyfiksem (XVIII w.), chór z późnogotyckimi płaskorzeźbami autorstwa Stanisława Stwosza (syna słynnego Wita - XVI w.), wczesnobarokowy ołtarz główny (XVII w.), dwa późnobarokowe ołtarze boczne (XVIII w.), malowany na desce obraz przedstawiający św. Marcina autorstwa prawdopodobnie Tomasza Dolabelli (1 poł. XVII w.), dzwon z 1606 r. oraz wiele innych cennych obiektów.
Kościół ustawiony jest na wzgórzu św. Marcina, z którego rozciąga się rozległy widok na Tarnów i okolice. Dookoła budynku, w obrębie ogrodzenia, istniał częściowo zatarty dziś cmentarz z XVI w. (zamknięty w 1861 r.). Kościół został wpisany do rejestru zabytków w 1961. Znajduje się również na Szlaku Architektury Drewnianej w Małopolsce.