"Huelva en la historia quedó,
con honra debe llevarlo;
que el gran Cristóbal Colón
salió del puerto de Palos
y América descubrió".
(Fandango popular)
La ciudad fue bajo la dominación musulmana una alquería que formaba parte de la jurisdicción de Niebla, dedicándose sus habitantes a actividades agrícolas y ganaderas. Fue conquistada por los cristianos entre 1239 y 1240. Su señorío fue donado por Alfonso XI en 1322 a Alfonso Carro y Berenguela Gómez. En 1279, Juan I cedió el término a Alvar Pérez de Guzmán. A partir de esta época la ciudad comienza a progresar, dedicándose sus habitantes a actividades marítimas. Aunque ya era puerto de importancia, Palos saltó a la Historia y se hizo un lugar privilegiado en ella porque desde aquí partió Cristóbal Colón el día 3 de agosto de 1492 en el viaje que lo llevaría a descubrir América. De Palos eran también los hermanos Pinzón: Martín Alonso y Vicente, los dos capitanes que acompañaron a Colón en este viaje.
La época dorada de Palos fue el siglo XV, cuando las expediciones navales castellanas contaban con la insustituible presencia de los expertos marinos palermos.
La paz de AlcaÇovas, firmada con Portugal en 1479, consideró las expediciones a Nueva Guinea constitutivas de delito, y por esta causa, los palermos fueron obligados a servir a la Corona con carabelas construidas en sus astilleros y aparejadas a costa de la población. Los Reyes Católicos ordenaron en 1492 que fueran puestas al servicio de Cristóbal Colón, reduciendo de esta forma los gastos del viaje y vinculando a Palos a la gesta.
El libro 'Expedientes carcelarios de Palos de la Frontera (Huelva). Prisión Provincial, 1936-1939' (Facediciones, 2008), de Juan José Antequera Luengo y Juan José Luengo Jiménez, da cuenta de cuantos vecinos sufrieron prisión durante la guerra civil española.