Al llegar al Pantano Dustwallow, Vol'jin pone al corriente a Rexxar y sus compañeros de cómo llegar a la Isla Theramore para platicar con Jaina Proudmoore y averiguar por qué los humanos atacaban a los orcos. Para esto, Vol'jin le proporcionó al maestro de las espadas Samuro, quién vive cercano a Theramore, unos barriles inestables para que los coloque en un campamento humano cercano a la isla para distraerlos y así permitirles a ellos entrar en la ciudad.
Cuando llegan con él, Samuro les dice que lo esperen hasta que él acabe, pero antes de actuar, Samuro elimina a su gran archienemigo, Bloodfeack el Berserker. Una vez acaba con él y los demás osobúhos, se dirige al campamento humano, teniendo que valerse de sus habilidades para avanzar a través de poderosas tropas y defensas humanas hasta colocar barriles en un cuartel, un taller, un santuario arcano y dos astilleros.
Cuando termina, regresa con Rexxar y sus compañeros y les informa de que ya es hora. Ellos parten en un barco y se encuentran a Jaina en la entrada de Theramore, pero al preguntarle sobre los ataques humanos, ella responde que no sabe nada, y accede a ver el campamento humano en la costa junto a ellos cuando les mencionan que estos les eran hostiles. Cuando vuelven, el campamento está arrasado, y se ven varios cadáveres de humanos, al momento que encuentran a varios naga que los atacan. Para descubrir quién está detrás de las incursiones humanas, buscan sobrevivientes en las cercanías, pero deben luchar con muchos naga hasta llegar con Lady Darkscale, líder de los naga, pero parecía que sólo había cadáveres, entonces encuentran un soldado raso moribundo quien al ver a Jaina le dice que el "almirante" se pondrá muy feliz de verla sana y salva.
Jaina se altera por esto y teletransporta a ella misma y los demás de vueta a Theramore, dónde de pronto aparecen barcos de la marina de Kul'Tiras, junto con sus respectivos marineros, y el almirante de la marina y padre de Jaina, Daelin Proudmoore, quién al ver a su hija siente una gran felicidad y le dice que cuando se enteró de la caída de Lordaeron estaba devastado, pero se desconcerta al ver a Rexxar reconociéndolo como un ogro. Jaina intenta explicarle que la Horda ya no es su enemigo y que tienen su propio reino, pero este sigue odiando y guardando rencor a la Horda por todo lo que hicieron en Azeroth y Stormwind.
Ordena apresar a Rexxar, Rokhan, Chen y Misha, pero Jaina usa una ventisca para abrir una vía de escape para ellos. Luego de vencer a algunos espadachines de la armada, logran abrirse camino hasta alcanzar barcos humanos, los que luego de abrir las puertas interiores de Theramore, usan para escapar y volver al Pantano Dustwallow.
Le informan a Vol'jin la situación, quién les sugiere que pidan ayuda a los tauren de Mulgore, y que para ello hablen con Cairne Bloodhoof, el jefe tauren, mientras él informaba a Thrall.
Al llegar al poblado tauren, Rexxar le pregunta a Cairne por él mismo, sin saber que era él. Este le responde que era él, pero cuando Rexxar le habla de los humanos y la Horda necesitaba su ayuda, pero le dice que le diga a Thrall que él estaba muerto, como su corazón.
Entonces llega el teniente de Cairne, Tagar, quien les explica la situación del secuestro del hijo de Cairne, Baine Bloodhoof, a mano de los centauros, y que a pesar de los intentos de rescate de Baine, no han podido siquiera averiguar si sigue vivo, y Cairne está en depresión desde entonces. Les sugiere ir a ver a Bovan Windtotem, quien podría ayudarles, pero además les pide eliminar a las harías que asesinaban a sus manadas de kodos.
Los guerreros acaban con las harías, y una vez acaban, viajan a ver a Bovan Windtotem. Cuando llegan con él, este les dice que soñó con el campamento de los centauros y que Baine seguía vivo en algún lugar del campamento centauro. Entonces, Rexxar y sus compañeros, junto con Bovan y sus hermanos espiritus caminantes, se ponen en marcha asaltando el campamento centauro, reviviendo a los tauren muertos que encontraban en el camino.
Cuando llegan hasta Baine, los centauros preparan varias emboscadas y tapan los caminos, pero de todas formas, todos logran abrirse paso a través de las fuerzas de los centauros y regresar a Baine sano y salvo.
Al ver a su hijo, Cairne se alivia y disculpa por haber caído presa de la depreción, y pone a sus hermanos en marcha para luchar con la Horda una vez más, pero también dice que él irá con Rexxar.
Al estar de vuelta con Vol'jin, este les dice que un ogro llegó herido pidiendo ayuda, ya que el nuevo jefe del Clan Stonemaul, Kor'gall , era cruel y despiadado, condujiendo el clan a la ruina, por lo que Vol'jin ve esto como una oportunidad de aliarse con los ogros y atraerlos a su causa.
Rexxar y sus compañeros viajaron al pantano de los ogros, y al momento de llegar a la entrada y pedir paso, los ogros dijieron que sólo podría pasar sobre sus cadáveres. Al derrotarlos, Rexxar pide unirse al clan, pero Kor'gall le dice que sólo podrá hacerlo pasando la "Prueba de sangre" que consiste en eliminar a las criaturas en "El guantelete".
Rexxar combate a las criaturas, apoyado por Rokhan, Chen, Cairne y sus bestias, logrando triunfar, volviéndose miembro al volver con Kor'gall, pero cuando le pide luchar con la Horda, este dice que se separaron de los "débiles" orcos hace mucho tiempo, y mientras él gobierne, ningún Stonemaul ayudará a la Horda, por lo que Rexxar lo desafía a una lucha a muerte por el liderazgo del clan, sin "juguetes mágicos", sólo músculo y habilidad. Rexxar debe recurrir a sus fuerzas para vencer a Kor'gall, enviando a todos los Stonemaul a la guerra, mientras ellos lo obacioan.
Al regresar, Vol'jin le dice que Thrall está cerca de la línea principal en la Cala Tidefury, y cuando llegan con él, este le pide a Rexxar ciertos materiales para encantar el estandarte de guerra de la Horda, pero antes de entregrárlos en la línea principal, encuentran una aldea orca arrasada recientemente, y luego encuentran cerca a los prisioneros, cuyo líder era Mathogg, quién les dijo que necesitaban la llave que tenía el centauro Khan Grathor. Luego de derrotarlo, consiguen la llave y liberan a los orcos.
Además, viajan a varios pasadisos subterráneos, dónde aumentaron su fuerza y consiguieron varios objetos poderosos.
Una vez llegan a la Cala Tidefury, Thrall finaliza el hechizo y le otorga el estandarte a Rexxar, nombrándolo Campeón de la Horda. La Horda y los humanos entablan batalla, mientras Thrall defiende la base de la Horda, Rexxar y sus compañeros dirigen el ataque contra el castillo del almirante Proudmoore. Una vez la destruyen, se preparan para invadir Theramore y acabar la guerra humano-orco de una vez.