Long ago, I read an article about an experiment where chimpanzees in captivity were given a banana vending machine. The machine took tokens that the chimpanzees could earn doing various tasks.
The researchers soon found that the male chimps were earning tokens, getting bananas, and trading the bananas to the female chimps for sex.
I'd guess that fire-starter and flint-knapper are the two oldest actual professions, with their origins pre-dating the evolution of 'modern humans'. The so-called 'oldest profession' (prostitution) likely required the development of agricultural civilization and wouldn't be that viable within hunter-gatherer societies. Similar arguments apply to the origins of priests and kings, to some extent. Hunter-gatherer tribes might also have had tribal leaders, shamans, and sex-for-food dealings.
