Предыстория
События аддона происходят спустя несколько месяцев после окончания оригинального Warcraft 3. Вторжение Пылающего Легиона провалилось, но леса Ночных эльфов сильно пострадали, и сейчас они заняты по большей части возрождением родных лесов. Король Мертвых освободился от власти демонов, и теперь плетет свои собственные планы. Лордерон все еще находится во власти Плети и демонических военачальников из расы Натрезим (Повелителей ужаса), но те из людей, кто смог уцелеть, организовали сопротивление и вполне себе неплохо держатся, даже освободили Даларан. Великий герой Иллидан Ярость Бури, прозванный Предателем, окончательно превратился в демона и где-то скрывается. Его находит лорд Пылающего Легиона Кил-Джеден и предлагает сделку: он утолит мучающую Иллидана жажду магии, а Иллидан уничтожит Короля Мертвых, отбившегося от рук. Иллидан соглашается, и здесь, собственно, начинается первая кампания аддона.
Кампания Ночных Эльфов: Ужас из глубин
Протагонисткой кампании выступает Мэв Песнь Теней, Смотрящая в ночь, представительница нового класса героев своей расы и тюремщица Иллидана. Она преследует его, чтобы наказать за преступления и снова заточить в тюрьму. В своей погоне за Иллиданом Мэв сталкивается с его новыми союзниками — расой Наг, которых Иллидан поднял из морских глубин. Мэв удается выяснить, что эта раса — потомки тех Ночных эльфов древности, что были верны королеве Азаре, виновнице первого вторжения Пылающего Легиона. Также выясняется, что вместе с черепом Гул-Дана Иллидан получил и воспоминания великого орочьего колдуна былых времен. В частности, он узнал про Око Саргараса — могущественный артефакт, хранившийся на руинах Садаллара. Этот город, некогда бывший столицей Ночных Эльфов, погрузился на морское дно десять тысяч лет назад, но колдовство Гул-Дана подняло его из морских глубин. В гробнице Саргараса Гул-Дан нашел свою смерть, но Иллидану удается преуспеть там, где орк потерпел поражение, и захватить артефакт.
Погоня за Иллиданом приводит Мэв вместе с примкнувшими к ней Фарионом и Тиренд, героями оригинальной кампании Ночных эльфов, в Лордерон, опустошенный силами Плети. Там Мэв встречает Мстителей — тех высших эльфов, что пережили разрушение Кель-Таласа Артасом в Reign of Chaos, и их предводителя, принца Келя. Фарион отправляется поговорить с духами лордеронских лесов, а Тиренд и Мэв помогают Келю провести караван с припасами в недавно освобожденный силами Альянса Даларан, но караван попадает в засаду нежити. Тиренд остается прикрывать тылы отступающим солдатам, и из-за невероятной силы ее магии под ней ломается мост. Мэв лжет вернувшемуся Фариону, что она якобы видела, что армия Плети разорвала Тиренд на куски. Это было нужно ей, чтобы верховный друид не отвлекался на спасение возлюбленной, а помог ей против Иллидана; большую роль сыграла также личная неприязнь Мэв к Тиренд, которая когда-то увела у нее Фариона, и к тому же освободила Иллидана.
В Даларане Иллидан проводит ритуал, который должен был растопить Ледяную корону и уничтожить Короля Мертвых, но энергии Ока Саргараса, которое применялось в ритуале, были столь велики, что могли бы разорвать Азерот на части, подобно тому, как когда-то был расколот Дренор. Потому Кель, Мэв и Фарион прерывают ритуал, в последний момент добравшись до Иллидана и уничтожив заклинательниц-наг, проводивших обряд. Мэв собирается казнить Иллидана, но тут Фарион узнает, что Смотрящая в ночь солгала ему и Тиренд на самом деле жива. Иллидан предлагает ему помощь в спасении возлюбленной, и Фарион соглашается, не дав Мэв закончить казнь. Разъяренная Смотрящая покидает его. Иллидан вместе с Фарионом спасают Тиренд, после чего Фарион с Тиренд возвращаются в Калимдор, а Иллидан в сопровождении своих наг уходит в закат.
Кампания Альянса: Проклятие Мстителей
Протагонист кампании — Кель, принц кровавых эльфов (или Мстителей), о которых уже шла речь выше. Он представляет новый класс героев Альянса — Чародеев крови. Кель служит в составе осколков Альянса под командованием маршала Гаритоса. Гаритос — самоуверенный мерзавец, законченый расист, ненавидящий всех, кроме людей, и крайне посредственный полководец. Единственная причина, по которой он стал маршалом — жуткий кадровый голод, наступивший после фактической гибели Лордерона в ходе вторжения Плети и, впоследствии, Пылающего Легиона. Идут бои за Даларан, положение сил Альянса шаткое. Кель опаздывает к общему сбору войск из-за того, что помогал Ночным эльфам в предыдущей кампании, чем вызывает на себя гнев Гаритоса. Гаритос оставляет его ремонтировать обсерватории, с помощью которых можно мониторить перемещения войск Плети.
Вскоре после выполнения этого задания нежить переходит в контрнаступление. Гаритос, ненавидящий Келя, дает ему самоубийственное задание: остановить продвижение войск Плети, но при этом забирает у него все войска, кроме эльфийских. Геймплейно это заключается в невозможности нанимать стрелков, рыцарей, мортиры, вертолеты, паровые танки и грифонов. При этом вместо мечников Альянса у игрока будут уникальные мечники Высших эльфов, которые отличаются от людских только внешним видом, вместо стрелков — лучницы (рескин ночно-эльфийских). Без всех прочих придется обойтись, причем во всей кампании, кроме первой главы.
Вскоре начинается контратака сил нежити, Кель оказывается в практически безвыходном положении. Помощь приходит, откуда не ждали: со стороны нагов, слуг Иллидана, и их предводительницы, леди Вайши. Вайши рассказывает Келю, что его народ, как и все эльфы, зависим от магии (Наги, если что, тоже бывшие эльфы). На протяжении тысячелетий эту жажду утолял Солнечный источник Кель-Таласа, но теперь он осквернен, так что Мстителям грозит медленное увядание. Народу Келя нужен новый источник магической силы, и Вайши предлагает его: новым источником могут стать демоны и, в частности, Иллидан. Для этого необходимо присягнуть Иллидану на верность, отрекшись от Альянса. Поначалу Кель колеблется, но снова появляется Гаритос, подталкивая его в «нужную» сторону. Маршал обвиняет Келя и Мстителей в союзе с «омерзительными тварями» (собственно, Нагами) и бросает в темницы Даларана, чтобы потом казнить. В ночь перед казнью Келя и его эльфов спасают наги леди Вайши. Теперь Кель согласен примкнуть к Иллидану. Вместе с нагами Вайши они отступают в Дренор, где скрывается Иллидан, через портал, когда-то открытый Кел-Тузедом.
В Дреноре Иллидан попадает в плен к неотвратимо преследующей его Мэв. Кель и Вайши освобождают своего повелителя, и Мстители присягают Иллидану на верность. Взамен он открывает им правду о своих мотивах. Спустя некоторое время после гибели Архимонда Иллидану явился демон Кил-Джеден. Он предложил ему невероятное могущество, которого тот искал всю жизнь, в обмен на то, что Иллидан уничтожит Короля Мертвых, предводителя Плети, который отказался от службы Легиону. Око Саргераса нужно было Иллидану, чтобы растопить Ледяную Корону и выполнить задание демонов, но он потерпел неудачу, и теперь скрывается в Дреноре от гнева Кил-Джедена.
Иллидан, Кель и Вайши решают остаться в Дреноре навсегда. Иллидан принимает решение уничтожить демона Магтеридона, управляющего этим регионом Дренора. Этим они убьют двух зайцев: завоюют себе новую родину и обезопасят себя от слуг Легиона, которые могут узнать, куда скрылся Иллидан. Мстители и Наги (кстати, нам дадут поиграть и за них тоже) закрывают демонические врата, через которые Магтеридон вызывает подкрепления, а потом захватывают и его Темную цитадель. Но, к сожалению, план скрыться в Дреноре не удается: Кил-Джеден находит Иллидана и в его новом царстве. Демонический владыка в ярости, но Иллидан убеждает его, что это тактический ход: после поражения с Оком Саргераса ему нужно было собрать новые силы, чтобы продолжить воевать с Королем Мертвых. Он просит Кил-Джедена дать ему еще один шанс. Демон соглашается. Иллидан, Вайши и Кель со своими войсками возвращаются в Азерот и готовятся к отплытию в Нортренд.
Кампания Нежити: Повелитель Тьмы
Кампания, которая по количеству интриг и «игр в престолы» задвигает на задний план все предыдущие, вместе взятые. Самая длинная из всех. Также она интересна тем, что главных героев тут двое — у каждого отдельная сюжетная линия, и один из них — Артас — не поднимает уровень, а наоборот, постоянно слабеет, теряя уровень за уровнем после каждой заставки — таким образом игра показывает нам, что король мёртвых теряет силы и Артас вместе с ним. Первую миссию Артас начинает как Рыцарь смерти 10 уровня, в начале последней у него второй. Тем не менее, в последней миссии Артас наконец-то начинает набирать уровни снова, и его вполне можно обратно прокачать до десятого.
Кампания начинается с того, что Артас возвращается в Лордерон после долгого отсутствия. Восточные Королевства в основном контролируются теми из Повелителей Ужаса, кто не отправился с Архимондом и его демонами в Калимдор, а остался, так сказать, прикрывать тылы. Вплоть до возвращения Артеса Повелители не знали, что Архимонд погиб и Пылающий Легион разбит, и тщетно ждали дальнейших указаний. Артас, огорошив их этой новостью, объявляет, что Повелители Смерти более не нужны, Плеть повинуется только Нер-Зулу и ему, королю Лордерона. Изгнанные Натрезим бегут в столицу, чтобы обсудить дальнейшие действия, а Артес приступает к зачистке своего королевства от остатков людского населения. В этом ему помогают Кел-Тузед, уже знакомый нам по RoC, и превращенная в нежить Сильвана Ветрокрылая. Где-то за кадром она вернула себе тело, став из баньши Темной охотницей — героем-нежитью, который, тем не менее, в скирмише относится к нейтральным (может быть нанят в таверне любой расой).
Во время зачистки Артас видит первое видение от Нер-Зула, в котором он призывает его бросить все и плыть в Нортенд, чтобы спасти Ледяной Трон. Сила Короля Мертвых, и Артаса вместе с ним, начинает таять. Артас возвращается в столицу, чтобы приготовить все к отплытию, но на него нападают раннее отстраненные им от дел Повелители Ужаса, перехватившие контроль над частью его нежити. Также он теряет контроль над Сильваной и ее баньши. Теперь Сильвана свободна и жаждет мести как Артасу и Королю Мертвых, так и Повелителям Ужаса, за то, что они уничтожили Кель-Талас и превратили в нежить саму Сильвану. Артас слабеет все сильнее, но у него все же получается бежать из столицы, захваченной Повелителями, и пережить покушение Сильваны. Он отплывает в Нортренд, оставляя Кел-Тузеда присматривать за порядком.
Повелители Ужаса предлагают Сильване союз, но у нее другие планы. Используя навыки своих баньши, она захватывает контроль над лесными гноллами и бандитскими шайками. С этой импровизированной армией она громит первого из Повелителей — Вариматаса. Тот, однако же, умирать не хочет и вместо этого решает перейти на сторону Сильваны. Затем Сильвана расправляется с лордом Детероком, подчинившим себе нашего старого знакомого, маршала Гаритоса. С Гаритосом она заключает временный союз, чтобы выбить последнего Повелителя, Бальназара, из столицы, пообещав столицу Гаритосу. Люди и нежить Сильваны одерживают победу, но Сильвана предает Гаритоса, убивает его и оставляет столицу себе. Основав, таким образом, новое государство, она называет себя и своих сторонников Отрекшимися.
Тем временем Артас, прибыв в Нортренд, понимает, что времени спасти Нер-Зула у него нет: войска Иллидана уже вступили на территорию Ледяной Короны. К счастью, на помощь ему приходит Анубарак, предводитель паукообразной расы нерубианцев, давно порабощенной Плетью. Он представляет класс Повелитель Могил — нового героя Нежити. Анубарак говорит Артасу, что до Ледяного Трона можно добраться не через горы, а под ними, через туннели древнего нерубианского королевства Ажол-Неруб. Так Артас с Анубараком и поступают, прорубаясь сквозь недобитых гномов Мурадина, недобитых нерубов и странных существ без лиц, которых Анубарак требует убить поскорее. В итоге неживые короли прибывают к Нер-Зулу одновременно с Иллиданом. Разворачивается битва, в которой Артас берет под контроль четыре обелиска, открывающих вход к Королю Мертвых. Одолев Иллидана в поединке (некоторое время в фэндоме считалось, что убив), Артас прорывается к Нер-Зулу и сливается с ним воедино, став, таким образом, новым предводителем Плети и Королем Мертвых, независимым от демонов и кого бы то ни было еще. Финита ля комедия, продолжение уже в сюжетных линиях World of Warcraft.
Кампания Орды: Основание Дуротара
Кампания, не связанная сюжетно с тремя остальными. Выполнена в стиле партийной RPG: каждая глава состоит из нескольких карт, между которыми можно свободно перемещаться, строить ничего нельзя, играем только героями, максимальный уровень поднят до 15, много побочных квестов. Кстати, именно таким изначально планировался весь Warcraft 3, но в итоге близзы решили не изобретать велосипед и сохранить геймплейный костяк предыдущих частей. Выпускалась частями — в оригинальном Frozen Throne в этой кампании была только одна глава, остальные добавили в патче 1.15. Кампания повествует о том, как Орда нашла себе новый дом среди пустошей Калимдора и начала строить город Оргриммар, а также о проблемах, с которыми столкнулось молодое государство Тралла. И главную из этих проблем зовут лорд-адмирал Даэлин Праудмур — отец Джайны.