Het verhaal van het spel speelt zich af tussen De Hobbit en In de ban van de ring. De Doler Talion en de Elfensmid Celebrimbor hebben hun krachten gebundeld en hebben een nieuwe magische ring gesmeed in de strijd tegen Sauron en zijn leger. Samen proberen ze forten en vestingen te veroveren en Mordor voor eens en altijd terug te krijgen.