Ten thousand years before Neolithic farmers settled in permanent villages, hunter-gatherer groups of the Epipalaeolithic period (c. 22-11,600 cal BP) inhabited much of southwest Asia. The latest Epipalaeolithic phase (Natufian) is well-known for the appearance of stone-built houses, complex site organization, a sedentary lifestyle and social complexity--precursors for a Neolithic way of life. In contrast, pre-Natufian sites are much less well known and generally considered as campsites for small groups of seasonally-mobile hunter-gatherers. Work at the Early and Middle Epipalaeolithic aggregation site of Kharaneh IV in eastern Jordan highlights that some of these earlier sites were large aggregation base camps not unlike those of the Natufian and contributes to ongoing debates on their duration of occupation. Here we discuss the excavation of two 20,000-year-old hut structures at Kharaneh IV that pre-date the renowned stone houses of the Natufian. Exceptionally dense and extensive occupational deposits exhibit repeated habitation over prolonged periods, and contain structural remains associated with exotic and potentially symbolic caches of objects (shell, red ochre, and burnt horn cores) that indicate substantial settlement of the site pre-dating the Natufian and outside of the Natufian homeland as currently understood.