Omstreek de derde eeuw voor Christus vestigde de eerste mensen zich in het gebied van het huidige Palanga. Veel mensen waren handelslui, die handel dreven met barnsteen, dat vanuit de zee kwam aanspoelen. Rond de vijfde en zesde eeuw na Christus trokken steeds meer mensen richting het gebied.

In 1161 werd Palanga voor het eerst vermeld, toen koning Valdemar I van Denemarken met zijn leger aan land ging en een Kurisch kasteel buit maakte. Hoewel Palanga eerder vernoemd werd, wordt 1253 gezien als het ontstaan van de stad. In dit jaar werd Palanga voor het eerst vermeld in de historische bronnen van de Duitse Orde. Barnsteen en visserij deden de stad in de middeleeuwen uitgroeien tot een belangrijk centrum voor handel.

De burgers van Palanga hielden zich vanaf de dertiende eeuw voornamelijk bezig met visserij, handel in barnsteen, honing en bont.

Palanga heeft vele veroveraars gekend. Vikingen en Noormannen hadden hun zinnen gezet op het gebied, maar in de dertiende en veertiende eeuw kwamen ook vele kruisvaarders die het gebied verwoestten.

Langzaam vestigde zich ook mensen ten noorden van het gebied en in 1429 werd ‘Heilige Aa’ voor het eerst vermeld. Dit was een Duitse naam voor het huidige Šventoji. Het dorpje Būtingė, gelegen ten noorden van Šventoji, is ontstaan in 1507.

In de zestiende eeuw werd Palanga een belangrijke haven, die vooral gebruikt werd door Nederlandse, Zweedse en Engelse vaartuigen. Hoewel de haven nooit een gesloten inham of een goede riviermonding had, speelde deze een belangrijke rol in het economische leven van Litouwen. Tijdens de zestiende en zeventiende eeuw was er veel handel met Königsberg (Kaliningrad), Gdańsk, Liepaja, Riga en andere Baltische havens. De belangrijkste import artikelen waren: fabricaten, garen en band, zout, ijzer, wapens en goederen gehaald uit koloniën. De export bestond voornamelijk uit: hout, lijnzaad, honing, huiden en vee.

Jan Sobieski was koning en groothertog van het Pools-Litouwse rijk van 1674 tot 1696. Hij gaf in 1685 opdracht voor een tweede haven aan de Šventoji rivier. De havens van Palanga en Šventoji concurreerde sterk met Liepaja en Riga. Op verzoek van rijke kooplieden uit Riga, heeft de Zweedse vloot in 1701 de havens van Šventoji en Palanga vernietigd, tijdens de Grote Noordse oorlog. Deze oorlog vond plaats tussen 1700 en 1721 rond de landen aan de Oostzee. De strijd ging voornamelijk tussen Zweden en Rusland, Denemarken en Saksen. Vanaf 1701 raakte ook Polen en Litouwen in de strijd betrokken en vanaf 1715 deed ook Pruisen en het keurvorstendom Hannover mee aan de strijd. In de periode na de Grote Noordse Oorlog werd Rusland een grootmacht in Oost-Europa en de invloed van Zweden sterk beperkt.

Na de annexatie van Litouwen door Rusland in 1795, werd het bestuur van het gebied overgedragen aan generaal Platon Zubov. In 1801 ging de leiding over aan generaal Nesolovski.

De geschiedenis van het huidige vakantieoord werd sterk beïnvloed toen graaf Mykolas Tiškevičius, een kolonel uit het leger van de tsaar, in 1824 de stad Palanga kocht met zijn omgeving. Hij stichtte samen met zijn erfgenamen een landgoed in de nabijheid; creëerde een park, en financierde de bouw van verschillende gebouwen in Palanga.

Door contributie van de familie Tiškevičiai zijn in de stad vele interessante gebouwen en plaatsen gekomen. Er kwam een botanisch park, een nieuw paleis, een haven, een steenfabriek, een vakantieoord met sanatoria en een nieuwe kerk. In 1886 financierde Juozapas Tiškevičius de vestiging van het progymnasium in Palanga. In 1888 werd dankzij Juozapas Tiškevičius een 630 meter lange pier aangelegd van eikenhout, waardoor schepen Palanga beter konden bereiken.

Het voormalige paleis, gebouwd tussen 1893 en 1897 door van graaf Feliksas Tiškevičius, is tegenwoordig in gebruik als museum voor barnsteen. Om het paleis heen werd een prachtig park aangelegd met een oppervlakte van 86 hectare. Bonen, stuiken en planten werden vanuit verschillende landen naar Palanga gebracht.

Tuin voor het paleis van Feliksas Tiškevičius

Toen in 1864 het drukken van boeken in het Litouwse schrift werd verboden, werd Palanga een belangrijk gebied voor smokkel. Marcijonas Jurgaitis, dokter Liudas Vpneikis en notaris Jonas Kentra speelden een hoofdrol in deze culturele smokkelarij. Zij organiseerde een smokkelnetwerk en verspreiding van de clandestiene pers. Liudas Vaineikis werd gestraft met ongeveer 25 andere personen en gedeporteerd naar Siberië.

Tijdens de eerste wereldoorlog werd Palanga bezet door het Duitse leger. Zij vielen de stad op 23 maart 1915 binnen. Tussen 1919 en 1921 behoorde Palanga en Šventoji tot Letland, maar op 21 maart 1921 werd het overgedragen aan Litouwen.

In 1933 kreeg Palanga stadsrechten. Maar op 10 april 1938 had de stad weer te maken met tegenslag. Palanga grotendeels verwoest door brand. Ongeveer 1500 mensen werden hierdoor dakloos.

Op 22 juni 1941 wordt Palanga bezet door het Duitse leger. Deze bezetting duurt voort tot op 10 oktober 1944 het Sovjetleger Palanga in beslag neemt.

Voor de eerste wereldoorlog bezochten jaarlijks ongeveer 4.500 to 5000 mensen het oord aan de Baltische kust. Tijdens de Litouwse onafhankelijkheid tussen de twee wereldoorlogen door liep dit op tot 15.000 vakantiegangers. Tegenwoordig bezoeken ruim 100.000 mensen per jaar Palanga en zijn mooie zandstrand.