Abstract: This paper presents a palynological study of the archeological layers from the Neanderthal site Abrigo 3 del Complejo del Humo, in southern Spain (Málaga), with the aim of reconstructing the environmental conditions in the vicinity of this hominin site. The Upper Pleistocene vegetation and its variability are described, revealing a high diversity of thermophilous plant taxa throughout the cold dry phases, together with a long-term persistence of woody taxa, including Mediterranean, mesophytes, xerothermics and conifers. With the pollen records of Maytenus senegalensis as an outstanding finding, this study demonstrates the co-existence of temperate, Mediterranean and Ibero-Maghrebian angiosperms on the southern coastal plains of the Iberian Pleistocene where Neanderthals survived for a long time. It is therefore clear that Neanderthals and early Upper Paleolithic modern humans lived in a litoral refugium, which was a propitious environment for maintaining a high biodiversity, including potentially edible plant species. Besides, this coastal refugium offers broad possibilities for hunting, and interpopulational relationships through coastal platforms.