It depends on the meaning you give to the word "prostitution"
There's clear historical evidence that "sacred prostitution" was practiced from the beginning of time.
If you consider those acts true prostitution™, then there's evidence that prostitution is the oldest profession.
If you do not consider those acts true prostitution™, then they still serve as an explanation to where such a saying comes from.
A known example of a temple prostitute is Šamhat.
The epic of Gilgameš is
an epic poem from Mesopotamia, is amongst the earliest surviving works of literature.
according to Wikipedia. In particular the
"Old Babylonian" version of the epic dates to the 18th century BC and is titled Shūtur eli sharrī ("Surpassing All Other Kings").
In the slightly later Akkadian version you can find, in Tablet I:
The trapper's father spoke to him saying:
"My son, there lives in Uruk a certain Gilgamesh.
There is no one stronger than he,
he is as strong as the meteorite(?) of Anu.
Go, set off to Uruk,
tell Gilgamesh of this Man of Might.
He will give you the harlot Shamhat, take her with you.
The woman will overcome the fellow (?) as if she were strong.
When the animals are drinking at the watering place
have her take off her robe and expose her sex.
When he sees her he will draw near to her,
and his animals, who grew up in his wilderness, will be alien to him."
So it seems that it's certainly an ancient profession.
More in general, it is clear that in multiple cultures there was a huge overlap among the concepts of fertility cults and rites and prostitution. The above is just an example of a temple prostitute:
Sacred prostitution, temple prostitution, or religious prostitution is a practice of worship that includes hieros gamos or sacred marriage performed as a fertility rite and part of sacred sexual ritual.
According to the same source it was practiced in:
- Ancient Mesopotamia
- Old Buddhism
- Biblical times
Still, according to the well-referenced article on Wikipedia, there is some controversy on whether this was true prostitution™ or simple devotional sex. In any case, the traditional view is to call these acts prostitution.
Whether they were prostitutes or not, is a meaningless game of semantics and definitions. It is up to the reader to decide!