A troll faj pontos eredete nem ismert. Az biztos, hogy Azeroth korai éveiben két komoly birodalom alakult ki: a középső területeken az Amani, és a délkeleti dzsungelben a Gurubashi. Rajtuk kívül északon is létezett egy kisebb troll állam, Zul'Drak. A trollok első komoly ellensége a nyugaton élő rovarszerű aqirok birodalma, Azj'Aqir volt - a hosszú háborúban az egymást nem kedvelő Amani és Gurubashi trollok egymás mellett harcoltak az aqirokkal. Évezredekig harcoltak, de végső győzelmet nem arattak; viszont végül az aqirok egy része északra menekült, ahol megalapította Azjol-Nerub föld alatti birodalmát, míg a másik részük délre húzódott, ahol létrejött Ahn'Qiraj.
Ekkortájt jelentek meg a Well of Eternity környékén a night elfek. A trollok ellenük is folyamatosan harcoltak, de nem tudtak mit kezdeni az erőteljes arcane mágiával. Ráadásul a night elfek hasonlóan kegyetlen és vérszomjas ellenfélnek bizonyultak, mint a trollok maguk. Alig néhány év eltelte alatt a night elfek meghódították az ősi Kalimdor legnagyobb részét, és mind az Amani, mind a Gurubashi birodalom gyakorlatilag szétesett.



A helyzet a Sunderinggel változott meg jelentősebben. A trollok legnagyobb része az egykori Kalimdor keleti részén vészelte át a pusztulást, noha egy kisebb Gurubashi csoport, a Sandfury trollok az elsivatagosodó Tanarisban maradtak, míg a legelső trolltörzs, a Zandalari egy erős varázslattal mentette meg otthonát, ami ezután a Maelstromtől délre szigetként maradt fenn. A Gurubashi trollok törzsei ezután egymással háborúzva osztották fel maguk között a jelenleg Stranglethorn Vale-ként ismert területet. Azonban a pusztulás után sokat kellett nélkülöznie a trolloknak is - így az egyik törzs, a Hakkari végül egy sötét istenséghez fordult segítségért... ő volt Hakkar the Soulflayer.
Hakkar segített a troll törzseken, de cserébe lelkeket követelt magának, amikkel táplálkozhatott; és az volt a terve, hogy ha kellően megerősödik, akkor megjelenik személyesen is Azerothon. Legelvakultabb papjai, az Atal'aiok fel is készültek a megidézésére - de a Zandalari trollok vezetésével a Darkspear, Bloodscalp, Skullsplitter és Shatterspear törzsek szembeszálltak a Hakkari és a Gurubashi törzzsel, elűzték az Atal'ai papokat és megakadályozták Hakkar megidézését. A papok északkeletre, Swamp of Sorrowsba menekültek, ahol új templomot emeltek istenüknek - ám ezt Ysera megtámadta és elsüllyesztette.



Ezt követően a trollok ismét felosztották maguk között a dzsungelt, aminek a Darkspear törzs - a legkisebb a jungle trollok között - lett a vesztese, ugyanis el kellett hagyniuk Stranglethornt és a parttól nem messze egy szigetcsoportra, a Broken Islesre költöztek. Itt háborúba kerültek a naga Sea Witch által irányított murlocokkal, és ez majdnem a Darkspear trollok kihalásához vezetett. A legjobbkor érkezett a Medivh útmutatását követő, Lordaeronból menekülő Horde Thrall vezetésével - így sikerült elűzni a Sea Witchet, és elüldözni a murlocokat. A Darkspear trollok vezetője, Sen'jin azonban nem élte túl az összecsapást - feláldozták a murlocok; fia és utódja, Vol'jin hűséget fogadott Thrallnak és követte népével az orkokat Durotarba, ahol a parttól nem messze az Echo Isles szigetcsoporton telepedtek le. Innen akkor kellett tovább menekülniük, amikor Daelin Proudmoore flottája megtámadta a szigeteket. A Horde és Jaina Proudmoore végül legyőzték az admirális flottáját és visszaszerezték otthonukat.
Nem sokkal ezután azonban az egyik fiatal witch doctor, Zalazane elkezdte a befolyása alá vonni a törzs tagjainak elméjét - így Vol'jin elrendelte a többiek evakuálását. A trollok új otthona Durotar délkeleti partján Sen'jin Village lett, míg Vol'jin Orgrimmarban, Thrall tróntermében található meg. A Darkspear trollok a Horde egyik leghűségesebb tagjai, akik a Cataclysm eseményei után régi loa isteneik erejéhez fordultak ismét - és ezzel megjelent a trollok között is az alakváltó druidák kasztja.