2시대에 사우론이 엘프와 인간의 최후의 동맹과의 전투에서 절대반지를 잃고 파멸한 이후, 곤도르는 적이 돌아오는 것을 막기 위해 모르도르에 '검은 문'을 지어 감시하고 있었다.[1] 하지만 곤도르의 세력과 감시도 수많은 세월이 지나며 시들해지고 있을 무렵, 사우론이 모르도르로 돌아오게 된다. 사우론의 세 명의 검은 대장은 우루크 군세를 앞세워 검은 문과 모르도르를 순식간에 장악한 후 검은 문 대장 탈리온의 가족들을 살해하고 탈리온도 죽이며 '나에게 돌아오라 요정 군주여'라고 말하며 하늘을 바라본다.
탈리온은 망령 세계에서 깨어나 살해당한 아내와 아들을 보며 자신이 죽은 것인가 생각하는 와중에 망령이 된 어떤 요정 군주가 나타나 그대가 죽음으로부터 추방되었다고 알려주게 된다. 탈리온은 죽은 요정 군주와 일체화 되어 죽을 수도 없는 몸이 되었고 요정 군주는 이 저주를 풀려면 검은 손을 찾아야 한다고 말한다. 그리고 탈리온은 그 요정 군주와 함께 모르도르 한 가운데의 빛나는 탑위에 있는 자신을 확인하게 된다.
탈리온은 자신이 요정 군주와 일체화되어 새로운 능력을 얻었음을 알게된다. 그 요정군주는 우루크의 마음을 엿보아 정보를 캐낼 수 있는 능력이 있었고 그 능력을 통해서 사우론의 검은 손과 싸웠다는 노예에 대해 알아낸다. 그는 그 노예를 소유하고 있는 '노예상 기무브'를 죽이고 그에게 잡혀있었던 옛 동료이자 탈주자인 히르곤을 만나게 되며 히르곤은 검은 손에 대한 정보를 원한다면 추방자들의 캠프로 오라고 말한다. 그리고 탈리온은 그를 염탐하던 이상한 괴물을 목격하게 되고 요정 군주는 그 괴물이 자신과 연관되어 있음을 느낀다.
그 괴물의 흔적을 쫓던 탈리온은 이상한 유물을 발견하게 되고 그 유물을 집어들자 요정군주의 기억의 일부를 보게 되며 요정군주도 얼마간의 기억을 되찾게 된다. 그 기억은 요정군주가 누군가에게 가족이 몰살당하는 장면이었고 그는 그 고통이 탈리온과 자신을 이어주고 있을 것이라고 추측한다. 그리고 마침내 그들은 골룸을 찾게 되고 탈리온은 몰래 슬금거리던 골룸을 목을 잡아 제압한다. 요정군주는 골룸이 자신을 빛의 주인님(Bright Master)라고 부르는 것을 보고 자신을 볼 수 있다는 것을 깨닫고 자신의 기억을 담은 유물에게로 이끌어 달라고 얘기하게 된다. 골룸이 그 유물의 위치를 알며 그 기억을 보았고 망령이 된 요정군주의 모습을 볼 수 있는 것을 보면 이 요정군주의 정체와 그 둘 사이에 무슨 관계가 있는지를 얼핏 볼 수 있다.
골룸이 알려준 곳에서 탈리온은 유물들을 하나 하나 찾아내며 요정군주의 기억과 능력도 조금씩 되찾게 된다. 그리고 밝혀진 요정군주의 정체는 2시대 중간계 최고의 대장장이 켈레브림보르였다. 기억은 사우론이 '선물을 주는 자'로 나타나 켈레브림보르에게 세공망치를 바치고 힘의 반지들을 만드는 것까지 이어졌다. 탈리온은 반지를 만들던 그의 기억을 보고 그가 켈레브림보르라는 것을 알아차리고선 불쾌한 기억찾기에서 손 땔 겸 켈레브림보르에 대한 얘기만 알려주는 것으로 넘어가려고 하지만 골룸은 반지 제작자인 켈레브림보르가 그의 소중한 보물을 만들어주지 않을까라는 목적으로 그의 기억을 더 찾을 것을 요구한다.
탈리온은 우루크 요새 근처에서 묶여있는 우루크 대장 '겁쟁이' 랫백(Ratbag the Coward)을 발견한다. 랫백은 자기가 전쟁군주(워치프 Warchief)가 되게 도와주면 검은 대장들에 대해서 알려주겠다며 거래를 청하고 그 시작으로 탈리온의 도움을 받아 그의 라이벌을 죽여 승진하게 된다. 그리고 랫백은 전쟁군주의 보디가드인 대장 '쌍둥이' 브로그(Brogg the Twin)과의 결투를 신청하지만 그는 되려 랫백을 포박하여 처형식을 행한다. 하지만 아슬아슬하게 탈리온이 랫백을 구출하고 탈리온은 그에게 질려 랫백과의 관계를 끊으려는 순간 랫백은 자신이 죽은 보디가드 대신에 전쟁군주의 밑으로 들어가 전쟁군주의 뒤통수를 치겠다고 말하며 탈리온에게 또 한 번의 기회를 요구한다. 하지만(...) 알고보니 그 죽은 보디가드는 전쟁군주의 쌍둥이 형제였고 그를 죽인 것 때문에 랫백은 또(...) 처형당할 위기에서 탈리온에게 구출을 당한다. 탈리온은 랫백에게 그냥 숨어있다가 자기가 전쟁군주를 죽일 때 나타나 자리를 차지하기만 하라고 전한 후에 전쟁군주 '다른 쌍둥이' 모그(Mogg the Other Twin)를 살해한다. 랫백은 자기가 전쟁군주가 되었으니 자기 휘하의 우루크들이 탈리온을 귀찮게 하지 못하게 하겠다고 약속하지만 다른 전쟁군주들에 대해서는 말해 줄 것이 없다고 말한다.
탈주자의 캠프에 도착한 탈리온은 히르곤의 붙잡힌 부하들과 빼았긴 폭약을 되찾기 위한 히르곤의 계획에 참여하게 된다. 그리고 대신에 히르곤은 그를 검은 대장들에게 이끌어 주겠다고 얘기한다. 히르곤의 부하들은 노예들로 분장하다 잡힌 상태였고 우루크들은 아직 폭약의 비밀을 모르고 있었다. 그들은 우루크의 그로그주를 중독시켜 우루크들을 몰살시키고 포로들과 폭약을 구해낸다. 탈리온은 포로로 잡혀있었던 히르곤의 아내 에륀(Eryn)이 히르곤과 감격스런 상봉을 하는 것을 쓸쓸하게 쳐다보고 켈레브림보르는 언젠가는 우리도 평안을 얻게 될 것이라며 위로한다. 탈리온은 나머지 전쟁군주들도 죽이고 나서 사우론의 기념비를 파괴하는 히르곤의 계획에 동참한다. 그러자 검은 대장 중 한명인 사우론의 망치(The Hammer)가 나타났고 탈리온은 그를 살해한다. 그 후 누르넨 왕국의 리타리엘이 마르웬 여왕의 명을 받들어 탈리온을 누르넨 지역으로 부르게 된다.
궁전에 도착한 탈리온을 맞이한 사람은 반송장같이 늙은 마르웬 여왕이었다. 여왕은 환영을 보면서 탈리온에게 다른 유물들과 난쟁이를 찾으라고 명한다. 구울의 동굴 속에서 망치 유물을 발견한 후에 찾은 기억은 사우론의 절대반지 제작과 그의 배신에 관한 것이었다. 그 후 쫓아오는 구울 떼에게서 도망치던 와중 난쟁이 사냥꾼 토르빈(Torvin)을 만나게 된다. 사냥감(유물)을 뺏은 대신 자신과 사냥을 할 것을 요구하나 탈리온은 거절한다. 그러나 토르빈이 또 다른 유물에 관해 알려주겠다고 하자 결국은 토르빈을 돕기로 한다.
탈리온이 마르웬 여왕에게 돌아오니 그녀는 기운이 다해 헐떡이고 있었으며 탈리온이 그녀가 약을 마시는 것을 도운다. 탈리온이 그녀의 손에 그녀의 마법 지팡이를 쥐어주며 자신의 저주를 풀 수 있는 방법이 있느냐고 묻자 마르웬의 눈빛이 검게 바뀌며 탈리온이 피의 의식의 희생자라고 알려준다. 저주를 풀 수 있는 방법을 묻자 마르웬은 검은 손을 죽이고 모르도르를 차지하라고 하고 탈리온은 그에게는 그럴 만할 세력이 없고 곤도르는 도와주지 않을 것이라 말한다. 하지만 마르웬은 그의 능력으로 우루크의 군대를 만들면 되지 않느냐며 또 다른 유물이 있는 위치를 알려준다. 그 유물은 포로로 잡힌 마르웬의 부하들이 가지고 있기 때문에 서둘러야한다고 말해준다. 탈리온은 우루크 지배 능력을 발휘해 포로들을 구출해내고 유물을 받는다. 이번의 기억은 가족들을 지키려 사우론과 맞섰으나 결국 사로잡혀 절대반지의 힘으로 사우론에게 세뇌당한 켈레브림보르를 보여주었다.
탈리온이 돌아오자 마르웬 여왕은 그에게 왜 돌아왔냐고 물어보며 아직 할 일이 끝나지 않았다고 말한다. 그녀는 그에게 오크 대장을 전쟁군주로 만들라 한다. 그렇게 탈리온이 한 우루크 대장을 지배하고 그가 전쟁군주가 되는 것을 도와준 후에 마르웬에게 돌아온다. 그런데 갑자기 마르웬 여왕이 마법으로 켈레브림보르의 영을 탈리온에게서 빼내어 켈레브림보르에게 자신과 힘을 합쳐 사우론을 물리치자고 말한다. 옴싹달싹할 수 없게 된 탈리온은 리타리엘에게 여왕의 지팡이를 부수게 하여 켈레브림보르를 되찾았다. 지팡이가 부숴지자 마르웬 여왕을 감싸고 있던 속박이 풀려 비교적 젊은 모습으로 돌아온다. 그녀는 예전에 사루만에게 도움을 청하러 간 적이 있었는데 그 때 세뇌를 당했던 것이다.마르웬은 그에게 감사를 표한다.
탈리온은 토르빈에게서 짐승 길들이는 법을 배우며 토르빈의 목표인 거대한 백색 그라우그를 사냥하기 위한 준비를 한다. 그라우그의 굴에 들어가보니 그라우그는 굴을 비우고 있었고 그 둘은 매복을 준비한다. 그 와중 토르빈은 아버지의 유품이자 예전에 백색 그라우그한테 패했을 당시 잃어버렸던 자신의 도끼를 되찾고 탈리온은 유물을 발견하게 된다. 그 유물에서 탈리온은 켈레브림보르가 사우론에게 세뇌당해 절대반지 세공의 마지막 단계를 도우는 기억을 본다. 기억에서 깨어나 비몽사몽하는 사이에 그라우그는 돌아와 있었고 토르빈은 시선이 잠시 졸고있는 탈리온에게 쏠려있을 때 그라우그에게 당하게 된다. 탈리온은 그라우그와 치열한 전투를 벌이다 잡히고 말지만 그 사이에 깨어난 토르빈과의 합동 공격으로 백색 그라우그 사냥을 성공시킨다. 토르빈은 자신과 계속 함께할 것을 청하지만 탈리온은 자기의 일은 자기가 알아서 할 것이라며 거절한다. 토르빈은 그에게 나중에 살아남으면 청색산맥으로 와서 술이나 들이키자고 말하며 작별한다.
한편 리타리엘은 사우론의 탑에게 잡혀 탈리온을 불러들이기 위한 인질이 되었고 탈리온은 그녀를 구해낸다. 리타리엘이 탈리온에게 자신의 왕국과 함께 싸울 것을 청하지만 탈리온은 거절한다.
탈리온은 자신의 휘하에 있는 우루크 전쟁군주들을 이끌고 바랏두르를 공격하여 우루크들을 살육하지만 정작 바랏두르 본진에는 아무도 없었다. 그는 홀로 왕좌에 가는 도중 묶여있는 시체들을 통해 도발하는 사우론의 탑의 목소리를 듣고 왕좌에 앉아있는 사우론의 탑을 마주한다. 맞서 싸우려는 탈리온에게 사우론의 탑은 탈리온이 켈레브림보르와 하나가 되어 죽지 못하는 것은 검은 손의 저주 때문이 아니라 켈레브림보르의 선택이였음을 알려준다. 켈레브림보르는 탈리온을 통해 사우론에게 복수를 하려고 했던 것. 탈리온은 잠시 흔들리나 결국 싸움에 임하게 된다. 싸움 도중에 사우론의 탑은 계속 탈리온의 죽은 아들과 아내의 목소리를 들려주어 도발을 하고 그를 조롱한다. 전투 도중에 그가 사라져 탈리온이 그를 쫓아갔더니 그의 아내가 그 곳에 있었다. 하지만 이것은 탑의 함정이었다. 그가 탈리온을 죽이려는 순간 그에게 극도로 분노한 탈리온은 그를 떨쳐내고 무자비하게 난도질하여 탑을 살해한다. 싸움이 끝나고 탈리온은 켈레브림보르에게 당신이 날 속였다며 당신 때문에 나는 평안을 얻지 못하게 되었다고 소리지르고 켈레브림보르는 탈리온이 복수를 원하는 줄 알았다며 변명한다. 켈레브림보르는 자신이 언제든지 탈리온을 떠날 수 있지만 이 복수의 순환을 반복되게 하는 한가지, 사우론의 검은 손을 죽여야 한다고 말한다.
탈리온이 누르넨으로 돌아오니 궁전에는 아무도 없이 폐허가 되어있었고 그는 그 곳에서 사우론의 탑과 싸울 때 들었던 환청들과 검은 손의 목소리를 듣는다. 그 곳에는 골룸이 있었고 탈리온에게 마지막 유물을 전해준다. 기억 속에서는 마지막 세공을 마친 켈레브림보르가 방심한 사우론의 눈 앞에서 절대반지를 빼았고 운명의 산에서 탈출하는 장면이 보였다. 탈리온이 깨어나니 그들이 보물을 차지하려고 할 것이라는 것을 깨달은 골룸이 탈리온을 죽이려 들었으나 켈레브림보르는 반지의 소유권을 주장하며 골룸을 쫓아낸다.
운명의 산은 마침내 분화하고 탈리온은 자신의 우루크 군대를 이끌어 사우론의 발톱(Talons of Sauron)들과 싸운다. 사우론의 발톱들을 처치한 후에 검은 문에서 기다리고 있는 사우론의 검은 손을 만나러 간다. 검은 손은 켈레브림보르에게 마지막 기억을 전해준다. 켈레브림보르는 자신의 우루크 군대와 절대반지의 힘으로 사우론과 맞섰으나 마지막 순간에 반지가 배신하여 원래 주인의 손에 돌아가게 되어 패배한다. 사우론은 켈레브림보르 눈 앞에서 가족들을 죽인 후에 자신을 능멸한 켈레브림보르의 얼굴에 망치로 난도질을 하고 죽인 것이었다.
사우론의 검은 손은 탈리온과 켈레브림보르를 죽이려는 순간 갑자기 자신의 목을 벤다. 그러더니 켈레브림보르의 령이 그 몸에 흡수되고 탈리온은 피를 흘리며 옴싹달싹할 수 없게 되었다. 그리고 켈레브림보르의 빙의의 힘을 이용하여 사우론이 검은 손의 몸에 빙의하여 돌아오게 되었다. 사우론이 탈리온을 죽이려는 순간 사우론과 하나가 된 켈레브림보르가 사우론을 잠시 멈추게 하고 그 틈에 탈리온은 사우론을 무찌르고 쓰러진다.탈리온은 아내의 마지막 말을 떠올리며 일어나고 켈레브림보르는 이제 사우론의 검은 손은 죽었고 할 수 있는 것은 다했으니 평안을 얻을 때가 왔다고 말한다. 탈리온은 사우론을 막을 수 있는 기회가 왔음에도 불구하고 여기서 포기하고 아무것도 하지 않는다면 과연 앞으로 평안을 얻을 수 있는가 묻는다. 탈리온이 분화하고 있는 운명의 산을 바라보며 "새로운 반지를 위한 시간이 왔다"고 말하는 장면으로 게임은 끝이 난다.
[1] 물론 원작을 고려한다면 어처구니 없는 설정이다. 검은 문 자체는 모르도르로 들어오는 적을 막기 위해 사우론이 만들었기 때문.