Karalienė Bona 1540 m. įsakė seniūnijos valstiečiams visokeriopai remti Palangos bažnyčią. 1579 m. minimas Palangos klebonas. 1590 m. bažnyčiai dovanotas Paliepgirių kaimas (patvirtinta 1597 m.). Iki 1597 m. pastatyta bažnyčia (vietoj protestantų atimtos), 1613 m. įkurta parapija, 1640 m. – altarija.
1767 m. pastatyta nauja medinė bažnyčia. 1804–1862 m. veikė parapinė mokykla. 1871 m. į Palangą grįžo kunigas Vladislovas Duseika, 1863 m. už ryšius su sukilėliais buvo ištremtas (mirė 1890 m. Palangoje).
1898–1907 m. pastatyta dabartinė mūrinė bažnyčia (Karlo Eduardo Strandmano projektas). Trečdalį statybos išlaidų sumokėjo grafas Tiškevičius, kitas – parapijiečiai, vadovaujami klebono Juozapo Šniukštos.
Manoma, kad ant Birutės kalno XVI a. buvo koplyčia. Žemaičių vyskupijos konsistorija, remdamasi Rusijos įstatymų sąvado straipsniu, kuriuo bažnyčių ir koplyčių atstatymui nereikalaujama valdžios leidimo, 1866 m. pradžioje nusiuntė Palangos klebonui Steponavičiui mūrinės koplyčios projektą ir įsakė ją pastatyti ant Birutės kalno. 1866 m. teismo sprendimu įsakyta nugriauti baigiamą įrengti koplyčią. Gyventojams užprotestavus, koplyčia išsaugota ir stovi iki šiol. Ilgametis Palangos klebonas Jonas Ilskis (1907–1985) po Antrojo pasaulinio karo suimtas ir ištremtas. Į Lietuvą grįžo 1956 m.