Zandalar, home of the Zandalar Tribe, was once part of the ancient continent of Kalimdor. From this area both of the great troll empires arose, the Gurubashi and the Amani, as well as a host of smaller troll nations. The Amani and Gurubashi rarely warred with each other, instead combining their efforts to combat the Aqir of western Kalimdor, a ferocious and devious race of insects. Eventually the Aqir were banished to their furthest northern and southern outposts, to some day become the Silithids and Nerubians. While both empires enjoyed a brief period of prosperity, the onslaught of the night elves drove both empires into decline although neither was truly defeated.
After the Great Sundering, the witch doctors and priests of the Zandalar tribe scrambled to protect their homeland. Although they succeeded in doing so, the rest of the continent was split or sank beneath the waves with the death knell of the Well of Eternity.
Some time after the Great Sundering, the Gurubashi priests learned to communicate with a being known as Hakkar the Soulflayer. While he granted them great power with his blood magic, he demanded ever increasing sacrifices of souls to feed his power. In time the Gurubashi turned on Hakkar, along with his Atal'ai priests. With the assistance of the Zandalar and a vast contingent of other trolls, Hakkar and the Atal'ai were banished from Zul'Gurub. Fleeing into the Swamp of Sorrows, they constructed another temple to Hakkar which was subsequently destroyed by Ysera and the green dragonflight. The remnants of the Atal'ai huddled in their sunken temple for the next thousand years.
Eventually, the Atal'ai discovered that Hakkar the Soulflayer could be summoned only within the ancient capital of the Gurubashi, Zul'Gurub. Sneaking back into the city, the priests managed the unthinkable; the arrival of the fearsome Soulflayer, summoned into physical form on Azeroth for the first time by the Atal'ai priests. The surrounding tribes sent in several of their High Priests to attempt to quell the Soulflayer, but Hakkar twisted the avatars of the Loa gods to his will. The Zandalar tribe, learning of the arrival of the Soulflayer, established an expedition on Yojamaba Island to help recruit adventurers to help banish the Soulflayer once and for all.