Příběh hry začíná tehdy, kdy se orkskému vůdci - Thrallovi - zjeví prorok Medivh, který předpoví jemu a jeho lidu záhubu, pokud neodpluje na západ do vzdálené země Kalimdor. Thrall moudře uposlechne, sebere svůj lid a na západ se vydá. Děj se přesouvá do království lidí, do Lordaeronu, kde se princ Arthas Menethil s čarodějkou Jainou Proudmoore snaží eliminovat invazi „rasy“ nemrtvých, jejíž základem je otrávit hlavní zdroje obživy. Jak se Arthas probíjí řadami nemrtvých stupňuje se v něm nenávist a touha po pomstě, která ho vyžene do mraivých končin země Northendu, kam se vydá pronásledovat toho, kdo je za invazi odpovědný, a sice pána děsu Mal\'Ganise. Po Arthasovým odjezdu navštíví Jainu již zmíněný prorok a sdělí jí, že Arthase na cestě do mrazivé země čeká jen smrt a předpoví jí stejný osud jako Thrallovi a ona, stejně jako Thrall uposlechne. Mezitím se Arthas zmocní magického meče Mrazivého smutku, který mu sice pomůže zničit Mal\'Ganise, ale vysaje jeho duši a uvrhne ho do světa nemrtvých. Arthas se vrátí do Lordearonu, kde zabije své ho otce, krále Terenase a na příkaz pána děsu Tichondriuse rozpráší s armádou nemrtvých lidskou říši. Při ovládání Lordearonu oživí černokněžníka Kel\'Thuzada, který vyvolá mocného démona Archimonda. Mezitím se Thrall pouští do války s lidmi, kteří taktéž osídlili Kalimdor a spolčuje se s vůdcem tarů - Cairnem, který mu řekne kde najde proroka Medivha. Thrall se za ním vydá a náhodou se tam setká s Jainou, velitelkou posledních žijících lidí a Medivh jim oznámí, že se musí spojit, aby se ubránili Plamenné legii, jež již podlehli lidi v Lordearonu a začít osvobozením Thrallova bratra, velitele klanu Warsong, Gromma Helscreama, kterého ovládl Mannoroth, jeden z velitelů legie. To se jim společnými silami podaří a oba bratři společně zničí Mannorotha, přičemž Gromm zahyne. Příběh nyní opouští všechny tři rasy a posouvá se do středu Kalimdoru, do hlubokých lesů, kde žije prastarý národ temných elfů. I na tyto místa útočí nemrtvý a jejich útok se snaží zastavit kněžka Tyrande Whisperwind, která si na pomoc přivolá starého moudrého druida Malfuriona Stormrage a vysvobodí jeho slepého bratra, lovce démonů, Illidana, ačkoliv s tím Malfurion nesouhlasí. Na základě diskuze s pánem smrti Arthasem se Illidian proti vůli svých spojenců zmocní Guldanovy Lebky a stane se napůl démonem. Takto silný zabije dalšího z nižších velitelů legie, Tichondria a je elfy vyhnán. Nakonec se lidi, orkové a elfové spojí proti silám legie a nastraží past na jejich vůdce Archimonda, který se do ní chytí. Pokusí se vysát sílu ze stromu světa, ale spolu se stromem ho zničí tisíce prastarých bludiček, které strom chrání.
