The first settlement of Europe by modern humans is thought to have occurred between 50,000 and 40,000 calendar years ago (cal B.P.). In Europe, modern human remains of this time period are scarce and often are not associated with archaeology or originate from old excavations with no contextual information. Hence, the behavior of the first modern humans in Europe is still unknown. Aurignacian assemblages--demonstrably made by modern humans--are commonly used as proxies for the presence of fully behaviorally and anatomically modern humans. The site of Willendorf II (Austria) is well known for its Early Upper Paleolithic horizons, which are among the oldest in Europe. However, their age and attribution to the Aurignacian remain an issue of debate. Here, we show that archaeological horizon 3 (AH 3) consists of faunal remains and Early Aurignacian lithic artifacts. By using stratigraphic, paleoenvironmental, and chronological data, AH 3 is ascribed to the onset of Greenland Interstadial 11, around 43,500 cal B.P., and thus is older than any other Aurignacian assemblage. Furthermore, the AH 3 assemblage overlaps with the latest directly radiocarbon-dated Neanderthal remains, suggesting that Neanderthal and modern human presence overlapped in Europe for some millennia, possibly at rather close geographical range. Most importantly, for the first time to our knowledge, we have a high-resolution environmental context for an Early Aurignacian site in Central Europe, demonstrating an early appearance of behaviorally modern humans in a medium-cold steppe-type environment with some boreal trees along valleys around 43,500 cal B.P.