I actually wasted a few days of my life playing this game about two years ago, when I had nothing better to do. Master of Magic was released in 1995 by Simtex/MicroProse and plays like a cross between Civilization and Warlords II. You choose a wizard, pick a race (High Elves, Gnomes, you know, generic fantasy) and guide them to world domination by building cities, raising armies and eradicating the other wizards.
Each race has its own selection of units and buildings. The Civ aspect comes into play when you research new spells (instead of new technologies) and upgrade your cities as new buildings becomes available. The spells you can cast are plentiful and varied - there are area effect spells, summoning spells, elemental magic, and so on.
What blew me away about this game (almost twelve years ago, mind you) was its turn-based combat. Detailed and challenging, it took the Warlords characteristic and gave it an in-depth visual presentation. Another aspect about Master of Magic which resembles Warlords II is the presence of heroes and magical items. Late in the game heroes become very powerful, to the point where no army can defeat them. This is also the weak point of the game: balance. However, Master of Magic offers deep gameplay and variation, which is why you should try it.
Here's the direct link for downloading Master of Magic. You'll need DOSBox to run it.
There's also an Master of Magic clone for Windows XP available here, although flawed.