The Union of Races
As described in Part I, the initial formation of the Covenant Empire was the result of a war between the Sangheili and San'Shyuum. To prevent annihilation of either race, they decided to form an alliance, which was the basis for the Covenant Empire in 852 BCE.
The Covenant Empire was very successful, and both the Sangheili and San'Shyuum improved their technology up to Tier 2. This meant that the Covenant members could perform exceedingly accurate Slipspace navigation, near-instantaneous communication and man-portable application of energy manipulation. This technology allowed them to venture to previous uncharted worlds.
Taming of the Lekgolo
It was in the year 784 BCE that the Covenant stumbled upon the planet Te, inhabited by Lekgolo. The Covenant was searching for Forerunner artefacts, which were apparently present on Te. To the horror of the Covenant Hierarchs, the Lekgolo had used all present Forerunner artefacts as their source of food.
Hives of Lekgolo were found in the orbital rings surrounding their planet Te. The rings were in fact the destroyed remains of one of the ancient Forerunner installations in orbit. The relics had been on the Lekgolo's diet for several millennia, and the orbital rings around the giant were actually composed of digested-and-destroyed Forerunner relics that some of the Lekgolo had been consuming. Strangely, many of the Lekgolo colonies had very differing diets, as some would eat only Forerunner alloys, while other would eat everything except Forerunner materials.
The enraged Hierarchs sent large Sangheili forces to deal with the heretics, but the fighting was slow. As the Lekgolo inhabited the same ancient relics that were sacred to the Covenant. Simply annihilating the Lekgolo would have resulted in the destruction of some and/or all of those relics. To deal with the crisis on Te, the Hierarchs decided to create another Arbiter. This Arbiter suggested that they could be tamed and put to better uses as part of the Covenant Empire. The Arbiter was sent to Te and encountered very crude versions of the Mgalekgolo.
The Arbiter convinced the Lekgolo which did not consume Forerunner relics to join the Covenant. As the other branch of Lekgolo did consume Forerunner relics, they were marked for destruction. This extermination campaign proved to be difficult, as the Lekgolo were able to combine into powerful Mgalekgolo; consequently, the Lekgolo won most, if not all, ground engagements. The Covenant's forces were completely overwhelmed by the sheer size and ferocity of their foes. On the verge of defeat, the Covenant took desperate measures, threatening to orbitally bombard the planetary surface of Te unless the Mgalekgolo surrendered. As the Lekgolo surrendered, they were officially absorbed in the Covenant by the end of the year.
Growing the Covenant
With the addition of the Lekgolo, studying the Forerunner technology became much easier. The Lekgolo also received the gift of technology, and rose to the same Technology Tier as the rest of the Covenant. One of the greatest improvement was the thick armour and specialised assault cannon the Mgalekgolo could now wear. This alliance of species continued until the year 1112, when the Covenant discovered and absorbed the Yanme'e. As the Yanme'e had invented an anti-gravity system which allowed them to fly, they were given tasks which suited this unique ability. The Yanme'e were mostly given the job of maintenance, but were also allowed weaponry when the Covenant fought an enemy. They view the Hierarchs as "Queens", a remnant of their former hive lifestyle.
It is unknown when the Covenant discovered the Huragok, biological supercomputers that were created by the Forerunners. It is known that there existed a great animosity from the Yanme'e towards the Huragok, as they eventually took over maintenance when available. As Huragok were created by the Forerunners, they were much more familiar with Forerunner artefacts than the Yanme'e. They are the only known non-combatant race to ever serve the Covenant, though some are rigged to explode like suicide bombers. While they possess no true tissues or organs, their nano-mechanical surrogates so closely mimic their biological analogues that they seem almost indistinguishable to observers. Multiple gas-bladders serve as their method of locomotion, allowing them to float through the air even after their deaths. The bladders also serve as part of their respiratory system; if their gas bladders deflate, they will asphyxiate and die.
When the Covenant discovered the Kig-Yar race 1342, they were eager to absorb them as well. At this point, the Kig-Yar race consisted mostly of pirates and merchants, who initially resisted and fought against the Covenant. The Kig-Yar come from Eayn, a satellite of the Neptune size gas giant Chu'ot. Chu'ot in turn is part of the Y'Deio system, which consist of 3 planets and an asteroid belt. It was from these asteroids that the Kig-Yar were able to fight the Covenant at first. they quickly recognised that they were facing a superior force and submitted, taking on the role of explorers and traders (and often thieves and smugglers). The Kig-yar were also motivated by the potential trade and wealth the Covenant could provide.
Much later in the year 2142 the Covenant discovered the planet Balaho, in the Tala system. The planet was home to a large pre-industrial Unggoy population. Due to their lack of technology, the Unggoy were easily enslaved into the Covenant. Not believing them to be much of a threat, they were given places as cannon fodder in the Covenant Army, not even given weapons.
Over time there has grown a large disdain between Kig-Yar and Unggoy especially, and has been the reason for many fights and rebellions. One of these revolts truly changed the Unggoy's place in the Covenant, when the Covenant High Council refused to investigate the allegations the junior staffer Ord Casto about a plan by the Kig-Yar to poison Unggoy. While this poisoning would not result in the Unggoy's death, it would make them sterile and thus end the Unggoy race. The resulting Unggoy Rebellion was highly vicious and eventually had to be put down by the appointment of an Arbiter and the threat of glassing the Unggoy's homeworld. The Unggoy proved that they were not the cowards they had been long deemed, and could indeed be vicious fighters when provoked. After the uprising's conclusion, as was their tradition, the Sangheili forgave the surviving Unggoy and allowed them to enter the Covenant military as armed infantry units, rather than the unarmed cannon fodder as which they had previously served.
When the Covenant Empire discovered Doisac and its inhabitants, the Jiralhanae had progressed towards industrial status. Having just rediscovered radio and rocketry, the Jiralhanae were no match for the Covenant Empire. Having been quickly defeated, the Jiralhanae were welcomed into the Covenant. They were given the role as 'brute force' soldiers.
The Covenant had now grown into a large entity, with 8 members, all controlled by one religion. This did not prepare them however to their biggest challenge yet, humanity. Their initial encounter was bloody, but it would set something in motion which would change the structure of the entire galaxy.