En los meses siguientes a la Batalla del Monte Hyjal, Thrall levó a la Horda a Kalimdor para establecer ahí su nación, a la que llamaría Durotar en honor a su padre. Un mok'Nathal llamado Rexxar que vivía en Kalimdor como un ermitaño junto a su osa Misha, mientras viaja, ve a un orco luchando contra unos jabalís espinados, y lo asiste en la batalla, pero uno de ellos le da un golpe mortal en el estómago. El orco le dice que se llama Mogrin y que, a pesar de que su muerte fue honorable, falló en su misión de entregar su informe a Thrall. Rexxar acepta cumplir con la misión en su lugar, y le lleva el mensaje a Thrall.
Thrall lo recibe con mucha hospitalidad y le ofrece un techo, y este, para agrecerlo, asiste a algunos de los líderes de operaciones de Thrall, el incursor Nazgrel, líder de la vigilancia de los alrededores, Drek'thar, el vidente de la tienda de magia, y el goblin Gazlowe, jefe de operaciones goblin. Thrall ordena al troll Darkspear Rokhan, su mejor explorador, que sea compañero de Rexxar en sus misiones.
Nazgrel le pide que elimine a las harías y a Bloodfeather su líder, ya que estaban arrasando las caravanas de suministros de la Horda. Al conseguirlo, Nazgrel lo envía a la armería de Ogrimmar para que pueda recibir uno de los artefactos poderosos que no venden como un obsequio.
Drek'thar lo envía a Thunder Ridge para conseguir seis hierbas de trueno que necesitaba para una poción en la que trabajaba, pero no podía ir el sólo ya que los lagartos de trueno eran hostiles por alguna razón. Cuando regresa, se la da a Rexxar como obsequio.
Gazlowe le pide que asista a sus goblins en las minas, ya que mientras buscaban un suministro de agua, una de las explosiones causó que se abriera una cueva de la que salieron muchos kobolds, los que no permitían a los goblins continuar sus operaciones, así que Rexxar y los demás deben eliminarlos mientras los goblins destruían los pilares de apoyo. Cuando acaban, Gazlowe les proporciona unos guantes rúnicos y un pergamino arcano.
Mientras cumplían sus encargos, Rexxar, Rokhan y Misha se encontraron con Chen Stormstout, un alquimista pandaren, quien les pidió que reunieran unos ingredientes para su nueva bebida, y una vez los consiguieron, Chen le ofreció a Rexxar un trago, pero este estaba muy fuerte, y Rexxar le preguntó si estaba intentando matarlo, y este se da cuenta de que la bebida estaba mal preparada, pero les dice que mientras descubre como arreglarla, se unirá a ellos en sus viajes como agradecimiento.
Al explorar las cercanías de Ogrimmar, se encuentran con un poderoso kobold, Noggrin Onetooth, a quién derrotan, oudiendo obtener todo el oro que él y sus kobolds habían recolectado.
También encontraron a un chamán, Morg Wolfsong, quién fue atacado junto a sus hermanos por brujos orcos que aún adoraban a los demonios de la Legión de Fuego, y les robaron sus artefacto sagrado, así que Rexxar y sus compañeros los asesinaron y regresaron el artefacto a Morg, pero él dice que ya es demasiado tarde para él, y le obsequia el artefacto a Rexxar, así como una garra de chamán.
Al finalizar, Nazgrel informa a Thrall que han aparecido varios humanos en las costas del noreste de Ogrimmar, cerca del puesto de observación del teniente de Nazgrel: Gar'thok, entonces ellos se preparan para partir, pero Thrall le dice que además Drek'thar viajó a Thunder Ridge para ver a los lagartos de trueno, y que tal vez necesitaría ayuda, así que Rexxar, Rokhan, Chen y Misha van a ayudarlo. Cuando lo alcanzan, este les dice que estaba allí para averiguar por qué los lagartos de trueno eran hostiles, y que también quería recoger unos huevos de lagarto para averiguar sobre su desarrollo y ecosistema. Una vez acaban, encuentran un aserradero humano al lado de muchos árboles talados, descubriendo que esa fue la razón de la furia de los lagartos de trueno. Rexxar iba a destruir el aserradero, pero Drek'thar le dice que hicieron un pacto de no agresión con los humanos luego de la Batalla del Monte Hyjal.
Cuando regresan, Rexxar y sus compañeros viajan al puesto de Gar'thok para observar a los humanos desde un observatorio goblin, pero una pared de roca impedía el paso, así que tuvieron que pasar por el hogar de los jabalís espinados, donde además de eso, encontraron algunos ancestros elfos nocturnos corruptos con sátiros. Una vez llegan al final de la cueva, observan que la actividad humana es bastante dudosa, ya que estaban preparando a muchas fuerzas militares.
Al regresar con Thrall, le informan de la dudosa actividad humana y la tala de árboles, y Thrall se pregunta por qué, ya que Jaina no suele ser tan impulsiva. Nazgrel viaja con Rexxar al puesto de observación para hablar con Gar'thok, pero se encuentran con todo el puesto destruído y cadáveres con sangre fresca, lo que enfurece enormente a Nazgrel, quién impulsivamente avanza hacia el campamento humano, junto a Rexxar y los otros. Mientras avanzan, encuentran cadáveres de orcos y humanos, estando seguro de que fueron los humanos. Cuando encuentran el campamento humano, lo destruyen rápidamente, y luego vuelven con Thrall, informándole del ataque humano. Thrall les dice que viajen al hogar de Rokhan, las Islas Eco, ya que los trolls podrían estar en peligro.
Cuando llegan a la costa y comienzan a avanzar, se encuentran a varias criaturas, como acechadores de la jungla, cangrejos, mur'guls y gigantes marinos. Cuando llegan al poblado troll, Vol'jin, hijo de Sen'jin y nuevo líder de la tribu Darkspear, les informa que la flota humana ya está atacando, y que sus guerreros están luchando, pero los humanos dominan y atacan las cabañas troll con barcos acorazados.
Saben que no serán de mucha ayuda sin transportes, así que Vol'jin los convierte en espíritus de wyvern para dirigir a los jinetes de murciélago troll, logrando hundir los acorazados humanos salvando el poblado troll. Vol'jin los vuelve a su forma normal y les dice que para que todos los trolls abandonen las Islas Eco, deben encender las cinco antorchas troll, consiguiendo que los troll se retiren al Pantano Dustwallow.
Luego de eso y al volver a Ogrimmar, llega un mensaje que dice que los humanos quieren parlamentar con Thrall, pero Rexxar sospecha que es una trampa, así que lleva a Rokhan y Chen con él para ir al encuentro en lugar de Thrall.
Cuando llegan, aparece un escuadrón de asesinos, los que vencen, pero un capellán les dice que eso era sólo el comienzo, y no era nada comparado con lo que se acercaba. Cuando vuelven, le dicen a Thrall sobre la emboscada humana, por lo que este les dice que viajen al Pantano Dustwallow para hablar con Jaina y aclarar todo, proporcionándoles un dirigible goblin.