New human burials from northern Jordan provide important insights into the appearance of cemeteries and the nature of human-animal relationships within mortuary contexts during the Epipalaeolithic period (c. 23,000-11,600 cal BP) in the Levant, reinforcing a socio-ideological relationship that goes beyond predator-prey. Previous work suggests that archaeological features indicative of social complexity occur suddenly during the latest Epipalaeolithic phase, the Natufian (c. 14,500-11,600 cal BP). These features include sedentism, cemeteries, architecture, food production, including animal domestication, and burials with elaborate mortuary treatments. Our findings from the pre-Natufian (Middle Epipalaeolithic) cemetery of 'Uyun al-Hammam demonstrate that joint human-animal mortuary practices appear earlier in the Epipalaeolithic. We describe the earliest human-fox burial in the Near East, where the remains of dogs have been found associated with human burials at a number of Natufian sites. This is the first time that a fox has been documented in association with human interments pre-dating the Natufian and with a particular suite of grave goods. Analysis of the human and animal bones and their associated artefacts provides critical data on the nature and timing of these newly-developing relationships between people and animals prior to the appearance of domesticated dogs in the Natufian.