Miejscowość wymieniana już w XIV wieku. Początkowo była wsią należącą do rodu Kniehinieckich, a następnie stanowiła własność Buczackich. Wojewoda podolski Michał Buczacki wybudował tu w XV wieku pierwszy zamek i erygował pierwszą parafię katolicką. Chociaż Podhajce nie miały jeszcze praw miejskich (otrzymały je dopiero oficjalnie w 1539 r., gdy stanowiły własność Wolskich), w dokumentach nazywane już były miastem. Następnie, z rąk Wolskich, wskutek sprzedaży, stały się własnością Stanisława Golskiego, wojewody ruskiego. Golski wybudował tu okazały zamek, który co prawda oparł się najazdom tatarskim, ale nie uchronił miasta przed zniszczeniem.
Podhajce trzeba było na nowo lokować. Zofia Golska, bratowa Stanisława, ufundowała w 1634 r. kościół, którego ruiny stoją do dzisiaj w miasteczku. W tym czasie w Podhajcach mieszkały cztery narodowości: Rusini na północ od rynku, Polacy we wschodniej części miasta, Żydzi w południowej i Ormianie w zachodniej. Ci ostatni nie zagrzali tu długo miejsca i w XVIII w. nie ma już o nich wzmianek.
W 1641 r. Podhajce stały się własnością Potockich. Pierwszemu właścicielowi z tego rodu miasteczko zawdzięcza czasy swojej świetności. Był nim hetman wielki koronny i wojewoda bracławski i podolski Stanisław Rewera Potocki. Rozbudował miejscowy zamek oraz otoczył miasto murami obronnymi tak, że oparło się ono oblężeniu tatarskiemu w 1655 r. Żona hetmana Anna Mohylanka ufundowała tu cerkiew obronną. Stanisław Rewera Potocki zmarł w Podhajcach w 1667 r. i tu został pochowany w miejscowym kościele, w kaplicy stanowiącej mauzoleum rodowe. Niestety, do naszych czasów zachowała się jedynie zewnętrzna część tej kaplicy. Wewnątrz są fragmenty tablic epitafijnych z XIX w. Nie ma natomiast śladu po nagrobku hetmana.
W roku śmierci Stanisława Rewery Potockiego Jan Sobieski odniósł pod Podhajcami zwycięstwo nad przeważającymi wojskami tatarsko-kozackimi dowodzonymi przez Krym Gireja i hetmana Piotra Doroszenkę. W kościele podhajeckim podpisany został pokój z Tatarami, którzy uznali się za sojusznika Rzeczypospolitej i Kozakami Doroszenki, który uznał zwierzchność króla. Zwycięstwo pod Podhajcami Sobieskiemu przyniosło buławę wielkiego hetmana koronnego.
Druga bitwa pod Podhajcami miała miejsce w 1698 r. By uprzedzić polskie uderzenie na Mołdawię Turcja wysłała oddziały tatarskie na Podole. Pod Podhajcami doszło do bitwy, w wyniku której właściciel Podhajec, hetman polny koronny Szczęsny Potocki, dysponując, podobnie jak wcześniej Sobieski, zdecydowanie mniejszymi siłami, obronił miasto i zmusił Tatarów do odwrotu. Była to ostatnia bitwa polsko-tatarska w dziejach Rzeczypospolitej.
W 1772 r. Podhajce przeszły pod panowanie Austrii. Po Potockich właścicielami miasta byli Bielscy i Worcellowie, a w połowie XIX wieku książę Aleksander Romuald Czartoryski. Jego żona, księżna Marcelina z Radziwiłłów była znaną filantropką fundującą ochronki i szkoły dla dzieci wiejskich wokół Podhajec. Prywatnie znano ją jako wybitną pianistkę, uczennicę Fryderyka Chopina, uchodzącą za najlepszą interpretatorkę jego utworów. Jej salon podhajecki słynął z koncertów chopinowskich.
W 1867 r. Podhajce stały się siedzibą powiatu, a w 1909 r. połączone zostały linią kolejową ze Lwowem. W II połowie XIX wieku i do czasu wybuchu I wojny światowej miasto słynęło z wielkich targów na bydło, konie i świnie. W 1887 r. funkcjonowała czteroklasowa etatowa szkoła męska, zatrudniająca 7 nauczycieli oraz szpital na 60 łóżek.
I wojna światowa przyniosła Podhajcom spore zniszczenia. Walki toczyły się tutaj także w czasie wojny polsko-ukraińskiej o Galicję. Zginął podczas nich teść Stepana Bandery i pochowany został na cmentarzu podhajeckim.
Przed wybuchem II wojny światowej miasteczko liczyło około 7 tysięcy mieszkańców, z czego połowę stanowili Żydzi. Pełniły rolę stolicy powiatu w województwie tarnopolskim. W Podhajcach urodzili się Jan Łomnicki, wybitny reżyser, autor filmów „Dom” i „Jeszcze tylko ten las” oraz jego brat Tadeusz Łomnicki, niezapomniany odtwórca roli pułkownika Michała Wołodyjowskiego w „Panu Wołodyjowskim” oraz „Potopie”.
Po II wojnie światowej Podhajce były prawie całkowicie opuszczonym miastem. Żydów wymordowano, natomiast zdecydowana większość Polaków zmuszona została do wyjazdu. Na miejsce dawnej ludności napłynęli tu przesiedleni z Polski Ukraińcy i Łemkowie.
