When Rexxar, Chen and Rokhan arrive at the Troll base, Vol'jin tells them, that a blademaster, named Samuro, waiting for them, to help get to Theramore. Rexxar's party follows the way out of the settlement and arrive at Samuro's hut. Then the blademaster start his journey across the forest to the human base. Before he reach its gates, he found a band of wildkin under the leadership of Bloodbeak and destroyed it.
After this, Rexxar and his companions meet with Jaina Proudmoore, the leader of Theramore, and demands that she explains why she is launching unprovoked attacks against Durotar. Jaina is shocked by these accusations, and insists that she did no such thing and would never betray the pact. She offers to help Rexxar investigate the matter, only to discover that the human base has been razed by a race of serpents called the Naga. After defeating their leader, Jaina encounters a survivor, who is pleased that she had been found and that the Admiral will be overjoyed. Jaina recognizes the tabard on the shield and realizes who the real culprit is. Rexxar is confused, but follows her back to Theramore.
Once at Theramore, they discover soldiers from Kul Tiras led by Jaina's father, Admiral Daelin Proudmoore. Daelin is happy to see his daughter again, but then notices her unusual companions. Jaina tells him that the Horde is not their enemy anymore, but Daelin, having fought in a a war against the Orcs, refuses to listen. He only remembers the atrocities they committed and desires to exterminate them all. He usurps control of Theramore and orders his men to arrest Rexxar and his allies. Jaina clears a path for them and teleports herself away. Rexxar and his companions stow away on a human transport ship and escape Theramore.
Rexxar makes it back to the Darkspear base, and Vol'jin reassures him that he will send word to Thrall about Proudmoore's invasion. In the meantime, Rexxar seeks out to gather allies to help the Horde. He first goes to Mulgore, the home of the Tauren. Their Chieftain, Cairne Bloodhoof, an old friend of Thrall, is too depressed to offer any help. His second, Tagar explains that Cairne's son, Baine, had been kidnapped by the Centaur. With the help of Bovan Windtotem, Rexxar and his allies rescue Baine and return him to his father. Cairne is eternally grateful and pledges his forces to help Thrall. He also personally joins Rexxar's group.
After returning to the Darkspear base, Rexxar meets a wounded Ogre of the Stonemaul clan. He explains that a new Warlord named Kor'gall had taken control and killed many warriors. The injured ogre fear that Kor'gall would lead the clan to ruin. Rexxar decides to enlist the Ogres as well. Rexxar travels to Dustwallow Marsh and meets with Kor'gall. He asks to join their clan. Being half-ogre, Rexxar had the right to join, but Kor'gall wondered if he had the strength. He sent Rexxar to a place called the Gauntlet, where he would undergo the trial of strength. After defeating the beasts there, Rexxar returned and was made a member. Rexxar then requested that the clan aid the orcs, but Kor'gall refused, as the ogres left the orcs long ago. Rexxar then challenged Kor'gall for his leadership. Rexxar eventually defeats him and becomes Warlord. The ogres praise him as their leader, and Rexxar orders them to war.
Rexxar then returns to the Darkspear Tribe where Vol'jin informs him that Thrall has set up camp nearby. Rexxar meets with Thrall, who tasks him with gathering some ingredients to create a banner for the Horde. Rexxar does so and Thrall uses them to create a standard with enchantments. He names Rexxar as Champion of the Horde and asks him to hold the banner into war. Rexxar agrees to carry it with pride. Rexxar then leads an assault against Proudmoores' base and eventually destroys their citadel. Proudmoore and his forces retreat, but Thrall know that it is not over. As long as Proudmoore lives, he will never leave the orcs alone.
This act consists on ten maps: Coastal Base (where the protagonists must fight a ten foot tall Lady Darkscale to survive), Theramore Isle, Dustwallow Marsh, Mulgore, Tidefury Cove, Tomb of the Ancients, Den of the Lost, Magistrates Temple, and Outland Arena.