Paleolithic cave art is an exceptional archive of early human symbolic behavior, but because obtaining reliable dates has been difficult, its chronology is still poorly understood after more than a century of study. We present uranium-series disequilibrium dates of calcite deposits overlying or underlying art found in 11 caves, including the United Nations Educational, Scientific, and Cultural Organization (UNESCO) World Heritage sites of Altamira, El Castillo, and Tito Bustillo, Spain. The results demonstrate that the tradition of decorating caves extends back at least to the Early Aurignacian period, with minimum ages of 40.8 thousand years for a red disk, 37.3 thousand years for a hand stencil, and 35.6 thousand years for a claviform-like symbol. These minimum ages reveal either that cave art was a part of the cultural repertoire of the first anatomically modern humans in Europe or that perhaps Neandertals also engaged in painting caves.