Palos de la Frontera asub Pürenee poolsaare edelaosas, täpsemalt Huelva provintsis Tinto jõe vasakpoolsel kaldal. Kuigi selles piirkonnas on asustuse jälgi alates kiviajast, asutati Palos dokumentide kohaselt 1322. aastal. See oli aasta, mil Kastiilia kuningas Alfonso XI andis peale Niebla tagasivallutamist Alonso Carrole ja tema abikaasa Berenguela Gómezele õigused valitseda sealset elanikkonda. Tõeliseks Palose linna asutajaks peetakse aga Álvar Pérez de Guzmáni, üht Kastiilia kõrgaadlikku, kellele anti linn 1379. aastal, kui ta oli vaid 14-aastane. Tänu temale asustati Palose linna ümber 50 peret ja sealne põllumajanduslik olukord paranes kõvasti.
15. sajandi seitsmes aastakümme oli Palose kuldaeg. Eelnevatel aastatel läbis linn demograafilise ja majandusliku tõusuperioodi ning kõik see oli tänu meremeestele ja nende tegevusele selleks, et tagada edukad suhted Vahemere-äärse Euroopa ja Põhja-Atlandiga. Selle kümnendi esimestel aastatel algas sõda Kastiilia kuningriigi ja Portugali vahel. Sõja käigus saavutasid Palose meremehed rahvusvahelise kuulsuse, kuna olid Atlandil seilamises kõige asjatundlikumad. Kuid 1479. aastal tuli Kastiilia kuningriigil tunnistada allajäämist Alcaçovase rahus ja nad pidid loobuma kõikidest oma Atlandi-Aafrika merede ja maade õigustest (v.a. Kanaarid).
Palose linn on üks väga eriline koht, sest see on linn, kust Christoph Kolumbus, vennad Pinzónid ja nende kaaslased alustasid reisi, mis viis Ameerika avastamiseni. 3. augustil 1492. aastal asusid Palose sadamast teele karavellid La Niña ja La Pinta ning lipulaev Santa María. Karavellid ja lipulaev jõudsid Kariibi mere saartele 12. oktoobril. Santa María läks Ameerika vetes põhja, kuid karavellid naasid ja jõudsid Palosesse 15. märtsil 1493. aastal.
1642. aasta mais võttis linn ametlikult nime Palos de la Frontera, varem oli see lihtsalt Palos. 16. sajandi keskpaigas polnud seal piisavalt laevu selleks, et vedada Ameerikasse kõiki neid Palose meremehi, kes tahtsid minna avastama uut maailma. Seetõttu pidid paljud neist rändama teistesse linnadesse, et oma tööga jätkata. Kõige selle tulemusena jäi linn peaaegu inimtühjaks. 18. sajandi keskpaigas oli seal vaid 125 elanikku. Kuid sama sajandi lõpuaastatel otsustasid sinna asuda mõned katalaanidest investorid, et pühenduda veini tootmisele, ja koos nendega hakkas Palos de la Frontera rahvaarv jälle tasapisi kasvama.
See linn on eriline veel ka selle pärast, et 22. jaanuaril 1926. aastal algas Palos de la Fronterast Calzadilla kailt esimene edukas vesilennuki lend Euroopa ja Ameerika vahel. Vesilennuki nimi oli Plus Ultra ja see läbis kokku 10 247 kilomeetrit teekonnal, mis kestis 59 tundi ja 39 minutit, kuni jõudis Argentiinasse.