(Note: this version of events is based off of the Burning Crusade version of the draenei/eredar split.)
25,000 or so years ago, there were no draenei. This is because the word draenei means 'exiles' in the language of the eredar, the people who rose to civilization on the world of Argus. The eredar looked much as the draenei of today do, and they were prodigiously gifted, strong, intelligent and naturally capable of learning to channel magical energy of any variety. Using these abilities, they built a society that lasted for thousands of years, one that was so marvelous that it even drew the attention of the titan Sargeras.
Unfortunately, this was after Sargeras had decided that his fellow titans and their whole 'let's go from world to world changing things to be the way we would like them to be' deal was pointless and futile. Anger and resentment built up in the former champion of the Pantheon until he stalked away from his fellows, abandoning his purpose as a defender of their works and instead choosing to work against them. So resolved, he began building a mighty war host to take his war of total destruction across the myriad worlds studded like gems throughout the Great Dark Beyond. Races like the Annihilan (Pit Lords) made excellent shock troops, and the Nathrezim were perfect spies and infiltrators, but what Sargeras needed were generals. Beings who could lead his forces, who were naturally powerful, strong, and intelligent enough to guide and direct a universal crusade of total destruction. And on Argus, he found the eredar.
At the time the eredar were effectively lead by a triumvirate. Even today, their descendants the draenei often break into such groups to deal with tasks of importance. The eredar leadership consisted of Archimonde, Kil'Jaeden, and Velen. When Sargeras first appeared to them, still clad in his glorious presence as one of the titans, both Archimonde and Kil'jaeden were very interested in his offer of even greater power and a role of responsibility and leadership in his vast new undertaking. To travel the many worlds, see things no eredar had ever experienced before, wield power on a scale undreamt of! Only Velen, of the three, was hesitant. He didn't have any concrete reason to reject Sargeras' offer,and thus no real objection he could make to his friend Kil'jaeden, but something about the titan seemed wrong to Velen and his suspicions gnawed away at him.
A vision Velen saw of the truth... of Sargeras' supposedly benevolence exposed for the mad desire for destruction that it was, and the eredar twisted into loathsome parodies of themselves as they wreaked destruction and havoc in Sargeras' name... led to contact with the Naaru K'ure and gave Velen both the resolve and the means to flee Argus. The Naaru instructed Velen to gather his followers and retreat to the highest mountain on Argus, and retrieved the Prophet and his followers just before servants of Kil'jaeden and Archimonde (who had taken Sargeras up on his offer) nearly destroyed them.
It is this event that made them 'draenei', or exiles. From this moment, one race became two, with the eredar servants of dread Sargeras known as 'man'ari' by their former kin. In time the eredar of the Burning Legion would even embrace the word man'ari (meaning foulness or corruption) and use it to refer to themselves proudly. Every modern draenei must live with this knowledge, that his or her greatest enemies are also his or her former people, that the darkness has demonstrated it can corrupt even their closest kin. That it can corrupt anyone, even the mightiest of their people... even Archimonde and Kil'jaeden fell prey to its insidious influence. Only Velen escaped their fate, and only Velen led the remaining one third of their people away from Argus.
For thousands of years the following pattern repeated itself: Velen and the Naaru would find a new world for the draenei to settle on, only to be discovered by agents of Kil'jaeden who had taken Velen's decision as a personal affront (in great part due to their previously strong friendship - Kil'jaeden is said to have viewed Velen as a brother, or even more than a brother, almost another aspect of himself in Rise of the Horde) and who would not allow them to escape. Over and over again Velen had to use his prophetic gifts and the aid of the Naaru to escape Kil'jaeden and the Legion, who had only grown in numbers and power over the years. Finally, through a combination of luck and their combined abilities, they arrived on a world that would come to be named Draenor, or 'Exile's Refuge' in ereduin.
Well, when I say 'arrived' what I should probably be saying is 'crashed to the surface in an enormous crystalline ship that fused into a massive diamond on impact and which nearly killed the naaru K'ure, who was entombed within to regenerate and who drew the spirits of others to himself as he did so, leading to a tradition wherein orc shamans would be instructed to treat Oshu'gun as sacred and in so doing tend to K'ure during his regeneration' but that's a mouthful. Handful? I am typing this after all.
This world was a relatively pleasant one, quiet, with a variety of flora and fauna making it suitable for the draenei to live but without any real reason for the Legion to seek it out. It was inhabited by a race of intelligent beings who lived in a semi-nomadic hunter/gatherer clan structure. As each people had little the other wanted or understood, conflicts were rare among them, although it did puzzle the draenei to see their crash site become a holy site to the orcs. Velen himself mourned his friend entombed within the gleaming mountain and set forth to lead his people on their new world, and for uncounted centuries the two races existed in a state of wary peace. The orcs had other things to worry about like ogres and gronn, while the draenei lived relatively free of those concerns in cities like Shattrah or Telmor, which was protected by a powerful crystal artifact.
This was the cycle of life on Draenor for millennia.