The trolls of Warcraft have a history that spans back further than any other playable race currently in the game, with the exception of the draenei. This makes it difficult to trace the entirety of their history, but fortunately the Darkspear of the Horde are one small fraction of what is a gigantic race as a whole. While the orcs, blood elves, Forsaken and tauren are all dealing with their own issues, the trolls of the Darkspear tribe are working quietly and largely by themselves to deal with a few major problems of their own.
The troll races of Warcraft were originally largely part of two major empires -- the Gurubashi of southeastern Kalimdor, and the Amani in the middle regions of the continent. There were other tribes scattered here and there, notably the trolls of Gundrak to the north, but by and large, all troll tribes fell under either the Gurubashi or the Amani empires. Prior to the Sundering, the trolls comprised a gigantic portion of the world's population, and while the Gurubashi and Amani didn't really like each other, they rarely warred, instead choosing to fight against a third empire, that of the Aqir. The two races fought relentlessly for thousands of years, and eventually the Aqir Empire split into two city-states, Azjol-Nerub to the north, and Ahn'Qiraj to the south. With the Aqir driven into exile, the trolls returned to their normal lives, though neither empire expanded much further than their original boundaries.