The question refers to Yoga as a form of physical exercise, breathing exercise with spiritual elements and not the word itself.
Yoga is a very broad term, the one which is known popularly is Hatha Yoga. This is different from Gyana Yoga, Raja Yoga, Bhakti Yoga and all the other forms desribed in various scriptures.
Lord Shiva is credited with propunding Hatha Yoga, interestingly the fish which overheard him instructing Devi Parvati on the details later became a siddha known as Matsyendranath. Matsyendranath was a historical figure dating back to the early parts of 10th century CE. He was the teacher of Gorakhnath alongwith whom he is said to have founded Hatha Yoga.
However, the asanas and breathing exercises that make up popular Hatha Yoga today were mentioned by Patanjali as two of the limbs of Yoga in his sutras. This dates back to the 2nd century BCE.
(Short answer: at least very much more than 5000 years)
It really loose in time. But, at least we can say that:
In his paper, The Indus Valley Origin of Yoga Practice, he suggests that Yoga was known and practiced by the people of Indus Valley civilization.
and keep saying
The person on the seal is seated with his legs drawn close to the body with two heels touching, which A L Basham calls, “a posture quite impossible for the average westerner”. This posture, has been identified by Yan as Mulabandhasana, which is difficult even for people who practice Yoga
and that was not the only seal
The same posture has been depicted on all five proto-Siva seals found disproving the theory that it was the work of an imaginative artist. Besides this other seals have been found with figures in other yoga postures suggesting that people in the Indus valley were the practitioners of Yoga.
So, we are talking of at least 4000~5000 years old from now.
On the other hand, we can read in Bhagavad Gita chapter 4, verse 29, 30, that
apāne juhvati prāṇaṁ prāṇe ’pānaṁ tathāpare prāṇāpāna-gatī ruddhvā prāṇāyāma-parāyaṇāḥ apare niyatāhārāḥ prāṇān prāṇeṣhu juhvati sarve ’pyete yajña-vido yajña-kṣhapita-kalmaṣhāḥ
(look word pranayama on 2nd line) Which according to this can be translated as
Still others offer as sacrifice the outgoing breath in the incoming breath, while some offer the incoming breath into the outgoing breath. Some arduously practice prāṇāyām and restrain the incoming and outgoing breaths, purely absorbed in the regulation of the life-energy. Yet others curtail their food intake and offer the breath into the life-energy as sacrifice. All these knowers of sacrifice are cleansed of their impurities as a result of such performances.
So, that means at least before kali yuga, which means, very much more than 5000 years from now
I cannot remember other if there is some pranayama explanation on older texts as upanishad, but is dificult to say time of some of that texts.