Two sites of the Neandertal-associated Middle Paleolithic of Iberia, dated to as early as approximately 50,000 years ago, yielded perforated and pigment-stained marine shells. At Cueva de los Aviones, three umbo-perforated valves of Acanthocardia and Glycymeris were found alongside lumps of yellow and red colorants, and residues preserved inside a Spondylus shell consist of a red lepidocrocite base mixed with ground, dark red-to-black fragments of hematite and pyrite. A perforated Pecten shell, painted on its external, white side with an orange mix of goethite and hematite, was abandoned after breakage at Cueva Antón, 60 km inland. Comparable early modern human-associated material from Africa and the Near East is widely accepted as evidence for body ornamentation, implying behavioral modernity. The Iberian finds show that European Neandertals were no different from coeval Africans in this regard, countering genetic/cognitive explanations for the emergence of symbolism and strengthening demographic/social ones.