Determining the extent of overlap between modern humans and other hominins in Eurasia, such as Neanderthals and Denisovans, is fundamental to understanding the nature of their interactions and what led to the disappearance of archaic hominins. Apart from a possible sporadic pulse recorded in Greece during the Middle Pleistocene, the first settlements of modern humans in Europe have been constrained to ~45,000 to 43,000 years ago. Here, we report hominin fossils from Grotte Mandrin in France that reveal the earliest known presence of modern humans in Europe between 56,800 and 51,700 years ago. This early modern human incursion in the Rhône Valley is associated with technologies unknown in any industry of that age outside Africa or the Levant. Mandrin documents the first alternating occupation of Neanderthals and modern humans, with a modern human fossil and associated Neronian lithic industry found stratigraphically between layers containing Neanderthal remains associated with Mousterian industries.