Сюжет WarCraft 3 The Frozen Throne начинается сразу после WarCraft 3. После разгрома пылающего легиона, ночные эльфы вернулись в глубь Ашенвальского леса, орда основала на востоке Калимдора поселение, там же при гнездились и люди. На другом конце света Иллидан вызывает древнюю расу Нагов. По пятам его преследует Мэйв, тюремщица которая на протяжении десяти тысяч лет охраняла Иллидана, дабы восстановить свою честь и вернуть Иллидана в темницу.
Цель Иллидана затопленный остров, который он поднимает со дна морского. Это оказывается тот самый остров где хранятся останки Саргареса, самого создателя пылающего легиона. С помощью черепа Саргареса Иллидан хотел уничтожить ледяной трон и Нер’зула. В ритуал вмешалась Мэйв, так как ритуал не был закончен, Король Мертвых не погиб, но при этом он очень сильно ослаб. Нер’зул взывает к своему первому рыцарю Артесу, который тот же час отправляется к Ледяной короне. Гонимые людьми, Высшие Эльфы объединяются с Иллиданом и пытаются уничтожить Ледяную Короную. В битве Иллидан серьезно ранен и отступает (это мы узнаем в World Of Warcraft). Артес поднимается в Ледяную Корону и сливается с Королем Мертвых. На свет появляется одно из самых мощных существ, которое ступало по землям Азерота.
В WarCraft 3 The Frozen Throne присутствует небольшая компания за орков, и является ответвление от главной сюжетной линии. Жанром дополнения является RPG и множеством элементов похоже на Diablo. Главным героем в ней является оркполукровка по имени Рексар, он объединяется с ордой, чтобы помочь отстроить и защитить Даротар. Эту компанию можно начать сразу после установке, не зависимо от основной компании WarCraft 3 The Frozen Throne.
