The extent and nature of symbolic behavior among Neandertals are obscure. Although evidence for Neandertal body ornamentation has been proposed, all cave painting has been attributed to modern humans. Here we present dating results for three sites in Spain that show that cave art emerged in Iberia substantially earlier than previously thought. Uranium-thorium (U-Th) dates on carbonate crusts overlying paintings provide minimum ages for a red linear motif in La Pasiega (Cantabria), a hand stencil in Maltravieso (Extremadura), and red-painted speleothems in Ardales (Andalucia). Collectively, these results show that cave art in Iberia is older than 64.8 thousand years (ka). This cave art is the earliest dated so far and predates, by at least 20 ka, the arrival of modern humans in Europe, which implies Neandertal authorship.