The Middle to Upper Palaeolithic transition in Europe witnessed the replacement and partial absorption of local Neanderthal populations by Homo sapiens populations of African origin(1). However, this process probably varied across regions and its details remain largely unknown. In particular, the duration of chronological overlap between the two groups is much debated, as are the implications of this overlap for the nature of the biological and cultural interactions between Neanderthals and H. sapiens. Here we report the discovery and direct dating of human remains found in association with Initial Upper Palaeolithic artefacts(2), from excavations at Bacho Kiro Cave (Bulgaria). Morphological analysis of a tooth and mitochondrial DNA from several hominin bone fragments, identified through proteomic screening, assign these finds to H. sapiens and link the expansion of Initial Upper Palaeolithic technologies with the spread of H. sapiens into the mid-latitudes of Eurasia before 45 thousand years ago(3). The excavations yielded a wealth of bone artefacts, including pendants manufactured from cave bear teeth that are reminiscent of those later produced by the last Neanderthals of western Europe(4-6). These finds are consistent with models based on the arrival of multiple waves of H. sapiens into Europe coming into contact with declining Neanderthal populations(7,8).