You start off with a fort (Kuwananjaa) and a couple of dwellings. As the newly uhm... «elected» tribe leader, Imani takes the tribe into the desert. Not much water there, so the mission is to find a way out before thirst and hunger overcome your people; you will lose 6 creatures each day, so get a move on. Since Imani needs to rest, you control the heroes Reem and Kibwe. Use Kibwe as your main hero (Reem can pick up gold in the desert), give him all your creatures and move northwest asap. Move until you find a broken bridge. Move around it and find the oasis. Once you're there, the daily death toll ends.
Pick up the free behemoths (behemoths, you'd be crazy to say no), but do not go further east yet. Instead, start clearing the western area of neutrals while trying to lose as few troops as possible. You could even return to base for reinforcements. Northwest of the oasis is an obelisk.
After you have cleared the site, go east. You will spot the Haven hero Melisande, who is on a crusader's mission to convert all heathens to dragon-ism. Convert or die, that's the deal. Once you spot her, she will make her way to you pretty fast, so get ready; visit both the Blind Maiden and the Rally Flag. Pass the flag and attack the Vigilant Sun fort. Rebuild it and wait for Melisande (she has the enemies' main army). When she attacks, fight for your life.
I managed to beat her since I had the defender's advantage, and in one of my most thrilling battles it ended up being a single behemoth left on my side against her last three stacks. I just managed it. After this, I sent caravans with units from the dwellings, and even though my one-behemoth army was attacked by the aggressive Melisande again before the caravan arrived, she did not have enough strength left to beat me. Tips for buffing the behemoths: regeneration, stoneskin and lightning burst.
With the new fort, you gain a foothold inside enemy lands. The main goal now is to take the Haven town of Castleroc, which is located in the northwest. Make your way slowly towards it while picking up as many resources as you can, and run back to the fort for new creatures shipped in by caravan. Roaming heroes may also have to be fought, which is why it may take a while. Eventually, you'll arrive at the town and take it. The enemy won't be able to launch a proper counter-offensive if you beat their main army already, nor will they have much of a defence in town.
Once you have it, you'll get access to a new Stronghold town (while losing access to the Haven town), and you will also gain control of the mines in the area. You can start building the town and consolidate your position. Visit the underground (stairway next to your town) to find some treasures. Keep sending caravans with reinforcements and clear the map of neutrals.
Moving north, you will encounter a wizard scouting army – a small contingent which should pose no serious threat to you. However, more are coming. Roaming Academy heroes will pop up and become stronger as time goes by. Keep building and fortifying your town, and keep shipping in caravans with troops. Just south of your Bloodforge there is an obelisk guarded by bone dragons. In the eastern part of the map, you will find some useful boosters and an Elemental Conflux. Soon enough, Asad himself will arrive with a sizeable army, but once you beat him, you get some development in the story and Imani becomes available.
There isn't much left, though; just hunt down the remaining Academy heroes and that's the end of the map.