The appearance of anatomically modern humans in Europe and the nature of the transition from the Middle to Upper Palaeolithic are matters of intense debate. Most researchers accept that before the arrival of anatomically modern humans, Neanderthals had adopted several 'transitional' technocomplexes. Two of these, the Uluzzian of southern Europe and the Châtelperronian of western Europe, are key to current interpretations regarding the timing of arrival of anatomically modern humans in the region and their potential interaction with Neanderthal populations. They are also central to current debates regarding the cognitive abilities of Neanderthals and the reasons behind their extinction. However, the actual fossil evidence associated with these assemblages is scant and fragmentary, and recent work has questioned the attribution of the Châtelperronian to Neanderthals on the basis of taphonomic mixing and lithic analysis. Here we reanalyse the deciduous molars from the Grotta del Cavallo (southern Italy), associated with the Uluzzian and originally classified as Neanderthal. Using two independent morphometric methods based on microtomographic data, we show that the Cavallo specimens can be attributed to anatomically modern humans. The secure context of the teeth provides crucial evidence that the makers of the Uluzzian technocomplex were therefore not Neanderthals. In addition, new chronometric data for the Uluzzian layers of Grotta del Cavallo obtained from associated shell beads and included within a Bayesian age model show that the teeth must date to ~45,000-43,000 calendar years before present. The Cavallo human remains are therefore the oldest known European anatomically modern humans, confirming a rapid dispersal of modern humans across the continent before the Aurignacian and the disappearance of Neanderthals.