When Rexxar, Chen and Rokhan arrive at the Troll base, Vol'jin tells them that a blademaster, named Samuro, is waiting for them to help get to Theramore. Rexxar's party follows the way out of the settlement and arrives at Samuro's hut. Then the blademaster starts his journey across the forest to the human base. Before he reaches its gates, he finds a band of wildkin under the leadership of Bloodbeak and destroys 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 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 Admiral 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 has taken control and killed many warriors. The injured ogre fears 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 has the right to join, but Kor'gall wonders if he has the strength. He sends Rexxar to a place called the Gauntlet, where he would undergo the trial of strength. After defeating the beasts there, Rexxar returns and is made a member. Rexxar then requests that the clan aid the orcs, but Kor'gall refuses, as the ogres left the orcs long ago. Rexxar then challenges Kor'gall for his leadership. Rexxar eventually defeats him and becomes the new 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 Admiral Proudmoore's 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 of 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.