The Bloodhoof tribe of tauren reside in the grasslands of Mulgore. They are members of the Horde and are led by Baine Bloodhoof who presides over the Tauren capital of Thunder Bluff. The tauren can be found in all areas of the world, trying to restore the balance of the world which was lost during the occupation of the Burning Legion. The tauren owe allegiance to Thrall and the Horde due to their assistance in ridding Mulgore of the marauding centaurs, thus giving the Tauren a place to call home.
Shortly before the Horde's arrival on Kalimdor, their ships were caught in a storm. While most of Thrall's soldiers made it to land, their ships were destroyed and they did not all make landfall at the same point. Thus Thrall set out with the soldiers who'd been on board his ship to search for the rest of his forces. After discovering signs of a recent battle during their exploration of the new land, they found a single bull-like humanoid (which they would later know was called a "tauren") being attacked by a group of "horse men" (which they would later be told were known as "centaurs"). Thrall attacked the centaurs but was too late to save the tauren's life. It wasn't long before they stumbled on a similar sight: two more injured tauren being overwhelmed by a centaur band. Again, Thrall and his orcs and trolls got involved on behalf of the tauren, and again were unable to save their lives despite killing the centaurs.
After finding some of his lost troops, Thrall's search for the others took him to higher ground, from which he was able to see a large army of centaurs in the canyon below. He noticed they were marching to the north.
Soon after that, Thrall's force was attacked by yet another centaur band. After once again routing the centaurs, Thrall was approached by a trio of tauren led by an aged, yet large and strong, tauren who introduced himself as Cairne. Cairne complimented the "greenskins" on their fighting prowess. Thrall told Cairne his name and that of his people, the orcs. He went on to say that they had come across the sea seeking their destiny. Cairne told Thrall that there was an Oracle to the north who might be able to help him, which prompted Thrall to mention the centaur army he had seen marching in that direction. Cairne was alarmed by the news, since it was clear to him that the centaurs were on their way to raid his village. He rushed off immediately along with his contingent. Wanting to learn more of the Oracle and also motivated by a desire to help, Thrall and his soldiers followed Cairne to the village where they successfully repulsed the centaur assault together.
After the battle, Cairne told Thrall of his tauren plight. The centaurs had driven off all the game in the region and, in order to avoid starving, the tauren would have to travel across the Barrens to Mulgore. Cairne worried that they would be overtaken by the swift centaurs before they could get there. Thrall pledged that he would escort the tauren to their destination and help protect their kodo beasts from attacks in return for being told the location of the Oracle. Cairne accepted the offer, and they were on their way. It was the beginning of a relationship of mutual respect and cooperation between the two peoples that continues to this day.
Thrall and his troops cleared the path of any centaurs standing in the way of the caravan while Cairne and his tauren fought off repeated attacks from behind aimed at the vulnerable kodos. When the caravan had almost reached its destination, Thrall saw a huge force of centaur charging at them. The orc Warchief despaired that they wouldn't make it. But Cairne would not allow himself to be defeated when he was so close to his objective, and used his might to start a rockslide that blocked the way of the centaurs.
The two peoples parted as friends, with the orc and troll force going to find the Oracle as well as their brethren (Grom Hellscream and his Warsongs were still unaccounted for), while the tauren left to search for a site on which to build their new home. Grateful for Thrall's assistance, Cairne gave him a number of kodos which proved to be quite useful as the Horde continued their journey.
During the Cataclysm the Bloodhoof tribe lost their leader, Cairne Bloodhoof. He was killed by Garrosh Hellscream, the newly-appointed Warchief of the Horde. Cairne had challenged Garrosh to a mak'gora- an orcish honor duel, due to his belief that young Garrosh had been secretly inciting war between the Horde and Alliance. It is customary in mak'gora for each combatant to choose a shaman to bless their weapon on the day of battle. Magatha Grimtotem approached Garrosh in secret and offered to bless his axe, Gorehowl. It was unknown to Garrosh at the time, but Magatha laced the blade of his axe with a lethal poison. Cairne was quickly killed in the duel, and Garrosh was enraged when he found out he had been tricked. A brutal and bloody struggle ensued as the Grimtotem, their ascension long in planning, invaded and cut down the tauren of Bloodhoof Village and Thunder Bluff. Baine Bloodhoof, Cairne's son, was only able to escape thanks to a Grimtotem that betrayed his tribe at the last minute and lead him to safety. The Grimtotem took and held Thunder Bluff, killing many of it's inhabitants, before the tauren took it back in a battle. The retaking of Thunder Bluff would not have been possible without the aid of the shaman and the goblins. Baine showed Magatha mercy, banishing her and her followers to the mountainous forests of Stonetalon. Any Grimtotem who wished it were allowed to safely defect from the Grimtotem and join the Horde.
Baine Bloodhoof now leads not only his tribe, but also the tauren people as a whole just as his father did.