The Natufians  populated an area that includes Palestine, Jordan, Syria, and Lebanon between 15,000 and 9,000 years ago. All the evidence indicates that they were East Africans, what the Bible calls "Kushite." They practiced the removal of teeth as an initiation rite, a trait of many Nilotic tribes.
Consider what these experts have to say:
Graeme Barker: "the similarities in the respective archaeological records of the Natufian culture of the Levant and of contemporary foragers in coastal North Africa across the late Pleistocene and early Holocene boundary".
Ofer Bar-Yosef cites the microburin technique and “microlithic forms such as arched backed bladelets and La Mouillah points" as well as the parthenocarpic figs found in Natufian territory originated in the Sudan. 
Christopher Ehret noted that the intensive use of plants among the Natufians was first found in Africa, as a precursor to the development of farming in the Fertile Crescent. 
That the Natufians were a Nilotic people is confirmed by the fact that Natufian physiology indicates a Mediterranean type with negroid affinities. (See Marcellin Boule, Henri Vallois, and René Verneau, Les Grottes Palaeolithiques de Beni Séghoual, pp. 212—214.) 
Natufian territory corresponds exactly to Horite territoryheld by Abraham's ancestors.
|Natufian territory corresponds exactly to Horite territory.|
When the Natufians lived in this area it received sufficient precipitation to sustain crops and orchards. Shrine priests
It is not far-fetched to state that the Natufians are probably the biblical Horites, whose religious beliefs and practices can be traced to the Upper Nile. The principal religious office of the Horites was that of the priest, so it is curious that archaeologists working at Hilazon Tachtit, near the Sea of Galilee, insist that this burial site suggests shamanic practices. Here is the pertinent section of their report:
The goods accompanying the burial are also typical of shaman burials. Tortoises, cow tails, eagle wings, and fur-bearing animals continue to play important symbolic and shamanistic roles in the spiritual arena of human cultures worldwide today [e.g., (28)]. It seems that the woman in the Natufian burial was perceived as being in a close relationship with these animal spirits. Shamans are universally recorded cross-culturally, in hunter gatherer groups and small-scale agricultural societies (25). Nevertheless, they have rarely been documented in the archaeological record [but see (29)], and none have been reported from the Paleolithic of Southwest Asia. Perhaps, it is not surprising if clear evidence for a shaman comes from the Natufian, as the profound social and economic changes associated with the transition to agriculture [the Neolithization process (6)] surfaced during the Natufian and undoubtedly entailed equally substantial ideological changes (30, 31, 32). Whether the changes in the spiritual outlook preceded and triggered the economic changes (33) or vice versa, an inseparable interplay is clearly observed between ideological and socioeconomic change across the forager-to-farmer transition. The unique grave at Hilazon Tachtit Cave provides us with rare concrete evidence for those processes in their initial stages at the termination of the Paleolithic on the eve of the Neolithic transformation. (From here.)
The report assumes that one of the buried women was a shaman, something that can't be ascertained from the evidence. Note that the report makes no specific connections between the supposed female shaman and observed shamanic practices. This is pure conjecture! It is highly unlikely that these people had both priests and shamans since the two offices represent distinct and contradictory worldviews. Shamanic practice involves traces in which the shaman mediates between the spirits of dead ancestors and the community. Such a practice was forbidden to priests, whose role was to mediate between the community and the Creator God.
The Natufians were more likely to have had priests since that office originates in the Nile region. That is not dismiss the evidence that this woman's burial clearly indicates that she was a woman of high rank among her people. However, we should not assume that she was a shaman when the symbolism of the animals found in her grave is easily explained in the context of the religious beliefs of the Upper Nile. These animals were sacred to the ancient Nubians and Kushites who had priests, not shamans. The two birds, which appear to be released from the woman's hand, likely represent the binary worldview of Abraham's ancestors and remind us of the two birds released by Noah. The leopard’s skin designated royalty and was worn over the shoulders by Kushite priests, with the paws crossed over the breast. The cow was the symbol of the Kushite celestial mother who was called Hat-Hor, the mother of Horus. Further, most of the animals found buried with the woman are mentioned in the book of Job and the genealogical information in the Bible reveals that Job was a Horite.
1. The British archaeologist Dorothy Gerrod coined the term "Natufian" because she was studying remains from the Shuqba cave at Wadi an-Natuf in Palestine. Therefore the term applies to a place, not a people.
2. Among the Luo tribe, for example, initiation involves the removal of six front teeth - three each from the upper and lower jaws. The Luo are a Nilotic tribe.
3. Barker G, Transitions to farming and pastoralism in North Africa, in Bellwood P, Renfrew C (2002), Examining the Farming/Language Dispersal Hypothesis, pp 151–161.
4. Bar-Yosef O., Pleistocene connections between Africa and SouthWest Asia: an archaeological perspective. The African Archaeological Review; Chapter 5, pg 29-38; Kislev ME, Hartmann A, Bar-Yosef O, Early domesticated fig in the Jordan Valley. Nature 312:1372–1374.
5. Ehret (2002) The Civilizations of Africa: A History to 1800. Charlottesville: University Press of Virginia
6. The French School of Anthropology developed under the influence of Paul Broca. Boule studied the Peking Man fossils, Henri Vallois served as Chair of the Museum of Natrural History in Paris from 1960 to 1967, and René Verneau studied paleolithic rock paintings in North Africa.
Related reading: Who Were the Kushites?; Abraham's Kushite Ancestors; The Christ in Nilotic Mythology