You start as Adar-Malik, on a mission to recover Vein's skull from those pesky wizards. The target is in the northwestern corner of the map, and you're in the opposite end, but since you aren't likely to succeed by simply walking in anyway, let's start by building your town and exploring your territory.
General tips: You should build town portal in your town. Then, when Adar-Malik needs reinforcements, you can just magic your way home to get them. Also, since you're really poor in the early stage of this map, try to build some wealth generators such as the town hall and resource silo. Spells are also important. I find the «fire wall» spell particularly useful, so level up your skills to boost that. Get the mage guilds up and running. You can defeat lots of neutrals here just by hammering away with fire spells. You can also call in reinforcements (without using a caravan) with the «instant reinforcements» adventure spell, that's really useful; you can get that spell at the shrine just east of the stables. As for other skills, I would focus on necromancy as it strenghens you while it weakens your opponents. I would also focus primarily on core creatures and not bother building elite dwellings until after you have control of mines. Last bit of general advice: go for gold early on, not experience.
As you begin exploring, you will soon notice that you're on an arid rock with no mines and limited resources, and a Simurgh standing in the way of further exploration. There's no other way: you have to fight this thing. I'd use your hero's spells for all they're worth.
When the bird has been defeated, head onwards and now you have a choice as to whether you go south across a bridge, into yellow player's extended territory, or continue west. If you go south, there is a fort way back to the east (almost exactly due south of your town), but if you go for this, lots of enemy heroes will come for you and take it back. I counted a full dozen heroes chasing. Going west, however, I did not experience this. So instead of taking the southern territory immediately, I recommend going west and fighting neutrals. Yellow player has a Haven town called Ziyad directly west of your starting town. This should be high on your list of priorities, but the enemy is strong so you may need to head back to your town to gather creatures. If you do manage to take it, beware: once you take a town, those spells you use to call reinforcements or withdraw back to your starting town will no longer work; the spells are applied to your nearest town. You can also move north; there is an Observatory which gives you a view of some of the area. I did eventually encounter a strong hero, so I retreated with the town portal spell to get creatures from the town. After getting some creatures, I went back out there and this time I crossed the bridge into the southern area. Fight the dragon, move on south and clear out this lush oasis. Moving eastwards, you will eventually find a fort, which you should take and rebuild to gain control of the mines in the area. Go and flag them. Once you own these, you control a Sawmill, a Gold Mine and an Ore Pit – all the three staple resources. You can now really start consolidating your position; use resources to buy as many creatures as possible.
If you have not yet taken the town of Ziyad, chances are the enemy will come for you. They really don't like that you control that fort and they want it back. Here are some good tips if you can't simply beat all of them: you can hide in the fort, you can summon instant reinforcements or you can run away with town portal if you want to. I managed to beat three big armies before having to run away from the fourth and concede the fort. Then I would just come back and reclaim it later. A more lasting solution, though, is to take the town to the west, as that seems to put a dent in their recruiting capabilities.
The dozens of heroes roaming all around is one of the real problems with this map. They will retake the forts if you leave them unguarded, and the same applies to towns. What to do? Well, you can hire heroes yourself. Some may be "stolen" from the enemy; if they're recruited by you, they won't be available to anyone else. Cool, right? The other thing is that sooner or later the enemies will start to run out of troops, whereas you will gain more and more through your necromancy skill. That's a skill you should really focus on. Eventually, you will have several heroes with armies guarding your towns, and the enemy heroes will start to run around with small or no armies at all, unable to take anything back.
North of your first town (go west first, then north, then east), you will find another fort (Muhiit Qsar). I found it protected by small armies only, and there are several mines around, so you should go for it to gain control of the area. Just north of the fort is an Academy town (Al-Amal). Take it! It's actually a really nice port town, and you can send out some ships! You can also start using Academy armies (disciples and rakshasas really kick butt), or you can take those recruits to your Necro town and turn them into undead units.
Southwest of this new town (down by the water's edge) there is an obelisk. Stop by, but make sure the town isn't taken by the roaming enemy heroes; there are a lot of them. While down by the water, head south and visit the Altar of Arkath too, so the seal is possible to open later. The seal is to the northwest of Al-Amal and leads to a Dragon Utopia.
Once you are strong enough to take and hold enemy towns, you should be able to hold all three eastern towns, thus controlling the eastern part of the map. You should soon be ready to move westward, but first, let's explore the possibilities on the water: When you manage to procure a ship, head north along the eastern edge of the map to find an obelisk. Further northeast there is a whirlpool, taking you to one of the inland lakes. Don't go too far north, though, that's enemy territory, and if you lose a hero there, they'll take your boat and have a shortcut down to your lands. If you bring a proper army, you may have more luck and the thing is: there's a fort up there, and the Altar of Ylath just northwest of that. The corresponding seal is to the south of your Haven town and beyond it lie some nice artefacts and some Shantiri ruins, and an obelisk.
Anyway, now that you control the east, let's go west. West of your Academy town (you have to go around the mountains) is a Gold Mine. That's one thing you really need: more gold, so go for it. There's a magic shrine nearby too. After that, keep heading west past the Haunted Ruins until you reach a garrison. You know what to do with it. Past the garrison are a pair of sphinx-like statues (taken straight outta «The neverending story»), and a cutscene gives you a hint that you can't go south until they're dealt with. Westwards it is, then. First, though, let me do you a big favour. Since you're here. Take a look at the picture below. See where my hero is standing, just north of those sphinxes and the stables? That's where you can find the Tear of Asha. Sod the obelisks and tell me I'm awesome.
Now move west. What have we here? Another town? Mine now. It's called Thaqib and it's another Academy town. You can really get some Academy armies up and running now. If you go north from Thaqib, you will approach your final destination; I wanted to explore the whole map first. Go south from Thaqib if you want to find an obelisk, and then go northeast from the town to find another one.
Heading east from Thaqib and then north as you reach the Blackfang Hideout, there's yet another town (Nudhar). It's problematic keeping hold of all these towns, that's why you should hire more heroes to guard them against enemy heroes with small armies. As they lose more towns, the enemies should have their recruiting capabilities hindered too. Many heroes will wander around with small armies (or none at all). With a total of three Academy towns at your disposal, gold and creatures are now available in vast numbers while the enemy is severely weakened.
At this point I started walking around with my main hero and an army of 1000+ skeletons, nothing else. The necromancy skill makes sure the army doesn't get depleted. My other heroes had Haven or Academy units, or elementals picked up from the confluxes.
To the east of Nudhar is a Bloodforge. Move north from the town to find a level-up shrine. Nice for your main hero. Go east from there to find another obelisk. Keep heading east and then north to find a fort. This is the same area you can access from the sea but should not take without a big army. At this point, however, it is easily controlled, and with that, you own everything except the final city.
There's still the matter of passing those guardian statues to the area in the south, however. Guess what, though: you're not supposed to. Insetad, attack the final city, Al-Jamasht.
Well, crap. Things are going to hell in a handbasket, aren't they. Don't worry, even though you are now the hunted traitor and your once-adored hierophant seems to have lost it completely, this is a story to be told, remember? This is what's supposed to happen. To make a point.
After the cutscene, run south. The stacks of grim reapers will not chase you. Go through the pass guarded by the statues. Keep heading south and you will complete the map.