20 Hauptmänner, 5 Häuptlinge und unzählige Soldaten bilden in Mordors Schatten Saurons Armee. Ihre Identitäten sind zunächst unbekannt und an Informationen zu ihnen ist mühsam heran zu kommen. Jeden Fußsoldaten, auf den ihr stoßt, könnt ihr mit der Macht des Geistes, der in Talion steckt, verhören und somit die Identität eines Hauptmanns aufdecken. Genau wie ihre Vor- und Nachnamen sind die Stärken und Schwächen der Hauptmänner zufällig zusammengewürfelt. Sie sind nicht nur bei jedem neuen Spiel anders, sondern wechseln im Laufe des Spiels durch die internen Machtkämpfe ständig. In Erfahrung könnt ihr diese Schwächen gegen bestimmte Fähigkeiten bringen, indem ihr gekennzeichnete Dokumente in Festungen findet, oder besonders vermerkte Soldaten aus der Armee des Hauptmanns verhört. Die Identität der fünf Häuptlinge hingegen, können nur Verhöre der Hauptmänner aufdecken. Obwohl Hauptmänner generell immer einem bestimmten Häuptling dienen, kennen sie ebenfalls die Stärken und Schwächen der anderen vier.

Zu Spielbeginn sind nicht nur alle 25 Uruks aus Saurons Armee unbekannt, sondern auch noch relativ schwach. Das bedeutet jedoch nicht, dass sie leicht zu bezwingen sind. Denn das gilt ebenso für Talions Fähigkeiten und so wird es am Anfang zweifellos geschehen, dass ihr Zweikämpfe gegen die Hauptmänner verliert und sterbt. Denn die Uruks halten zusammen. Bis zu fünf Hauptmänner können gleichzeitig in einem Untergebiet hausen und dem einen mit samt ihren Soldaten zur Hilfe eilen. So findet ihr euch schnell umzingelt wieder und erleidet mitunter eine tödliche Niederlage. Da Talion durch Celebrimbors Geist dazu verdammt ist, auf Mordor zu wandeln, steht er direkt am nächsten Turm wieder auf. Aber dieses Ereignis hat natürlich Folgen für Saurons Armee!

Wann immer Talion stirbt oder ihr Zeit verstreichen lasst (Funktion des Schmiedeturms), erhalten Hauptmänner Macht durch einen Sieg über euch. Das gilt übrigens für alle beteiligten Hauptmänner. Außerdem tragen mindestens vier von ihnen Aktionen untereinander aus. Das können tödliche Duelle mit anderen Hauptmännern, Festmale für ihre Untertanen oder eine Jagd sein. All das lässt den jeweiligen Hauptmann ein bis drei Macht gewinnen. Wodurch er für euch schwerer zu besiegen wird, aber auch bessere Beute bietet. Es ist daher nicht schlimm, wenn zu Beginn des Spiels Hauptmänner durch euch aufsteigen. Ihr werdet es ohnehin nicht schaffen, alle Hauptmänner dauerhaft tot zu halten. Dafür rücken neue zu schnell nach. Das Macht-Maximum für jeden Hauptmann beträgt jedoch 20.

An diesem Punkt lässt er bei seinem Tod höchstwahrscheinlich eine epische Rune für eine eurer Waffen zurück. Im späteren Spielverlauf könnt ihr beim Verhör eines beliebigen Uruks sogar "Todesdrohungen" (Stufe 4 Fähigkeit) gegen einen Hauptmann eurer Wahl aussprechen, wodurch dessen Macht augenblicklich um mehrere Punkte steigt und für euch die Wahrscheinlichkeit auf eine epische Rune erhöht. Auf diese Weise könnt ihr gute Waffenrunen gewissermaßen farmen.

Das Ziel des gesamten Armee Konzeptes ist es selbstverständlich die fünf Häuptlinge zu töten und damit an deren Meister zu kommen. Wie schon bei den Hauptmännern gelingt das durch einen Sieg im Kampf. Häuptlinge laufen jedoch meistens nicht frei durchs Land oder die Festungen. Es müssen spezielle Aufträge erfüllt werden, um sie herauszulocken und erst dann erhaltet ihr eine kurze Chance sie bekämpfen zu dürfen. Denn Häuptlinge können sich auch als feige oder ungeduldig herausstellen und einfach aus dem Kampf fliehen. Ein Verfolgung ist dann kaum möglich. Ihr müsst schlichtweg eure nächste Chance abwarten.