Niewielki miejski zamek w Podolińcu powstał na początku XV wieku. Szybko rozwijające się miasto obdarzone licznymi królewskimi przywilejami przed rokiem 1382 zostało obwarowane kamiennymi murami. W roku 1408 król Zygmunt Luksemburski oddał w lenno Imrichowi z Perina zamek Lubownia z okolicznymi ziemiami. Wśród nich było także miasto Podoliniec. W 1409 roku Imrich uzyskał od króla zezwolenie na wzniesienie w obrębie miasta zamku lub twierdzy z kamienia lub drzewa. Bardzo szybko bo już w 1412 roku w południowej części miasta obok bramy Górnej został zbudowany murowany zamek. Niewiele wiadomo o jego pierwotnym  wyglądzie. Zapewne miał plan zbliżony do trapezu. Posiadał budynek mieszkalny oparty o mur miejski być może z niedużą wieżą wystającą przed lico muru i zapewne jakieś zabudowania gospodarcze. Mimo iż powstał wewnątrz miasta oddzielony został od niego murem i fosą.

W 1412 roku Zygmunt Luksemburski nadał Podolińcowi status wolnego miasta królewskiego. W tym samym roku w Zagrzebiu Zygmunt Luksemburczyk wystawił dokument, na mocy którego w zamian za 37000 kop groszy praskich zastawił on Polsce Lubowlę, Podoliniec, Gniazdę i 13 miast spiskich. Ponieważ w tamtych czasach od pożyczonych pieniędzy nie pobierano odsetek zysk zapewniały dochody z zastawionego majątku. Wypłata pożyczki miała miejsce na zamku w Niedzicy i tu również miał mieć miejsce jej zwrot. Pieniądze nigdy nie zostały zwrócone Podolinie i pozostałe miasta spiskie przez 360 lat należały do Polski.

Podczas walk sukcesyjnych o tron węgierski w XV wieku na zamku stacjonowała stał polska załoga. Obronił się on przed atakiem husytów pod dowództwem Jana Jiskry tzw. bratrzyków. W roku 1591 starostwo spiskie wykupił Sebastian Lubomirski. W posiadaniu jego rodziny starostwo  w tym i miasto Podoliniec pozostawało przez następne 150 lat. Dwa lat później z inicjatywy Sebastiana przeprowadzony zostaje remont zamku. Syn Sebastiana Stanisław Lubomirski był zagorzałym zwolennikiem reformacji. Sprowadził do Podolińca zakon pijarów którzy wznieśli w mieście kolegium i szkołę. Poza murami miejskimi przy bramie Dolnej zbudowali klasztor i kościół. Nim  zakonnicy wznieśli klasztor użytkowali dwa zamkowe pomieszczenia. Ta informacja spowodowała że błędnie utożsamiano położenie zamku w sąsiedztwie zabudowań klasztornych.

Według zachowanego opisu z roku 1765 zamek miał formę niewielkiego pałacu. Piwnice mieściły spiżarnie pierwsza kondygnacja zajęta była przez zarządcze na drugiej znajdowało się pięć pokoi a na trzeciej trzy komnaty i duża sala reprezentacyjna. Już wtedy jednak ostatnia kondygnacja była w złym stanie i nie była użytkowana bo groziła zawaleniem.

Ostanie wzmianki o zamku pochodzą z roku 1871 i 1891. Zapewne pod koniec XVIII wieku zrujnowany zamek został rozebrany. Budynek pałacowy przebudowano pozbawiając go cech historycznych i zaadaptowano na potrzeby miasta. Obecnie mieści się w nim Urząd Miejski. Obok niego zachowały się fragmenty murów oraz baszty które są pozostałościami murów miejskich być może wykorzystanymi przy budowie zamku.