The first, to my knowledge, strategy role-playing game ever, King's Bounty was released by New World Computing around 1990 for DOS, the Sega Genesis, and the Commodore 64. The Heroes of Might & Magic series of games, also designed by Jon van Caneghem, is quite similar -- and the PlayStation 2 game Heroes of Might & Magic: Quest for the Dragonbone Staff is essentially the same thing repackaged, according to Game-Revolution's review.
The plot, admittedly, is nothing special: the evil Arech Dragonbreath (yes, that is his name, and yes, he is a dragon) has stolen the Sceptre of Order. For some reason known only to himself, he has put together a map of the area surrounding the Sceptre's hiding place; pieces have been left with his minions, and with eight mythical artifacts of no use to dragonkind. Meanwhile, good King Maximus, benevolent ruler of the Four Continents and all that, is dying without the artifact, and has commisioned you, a hero just returned from clearing out the vile dungeons of the realm, to get it back for him. Preferably with Arech's head on a platter.
Arech, of course, is not alone in his quest to kill the immortal king. Allied with him are sixteen other nefarious villains, most notably Urthrax Killspite, a chaotic demon who is prophesied to become the new King should Maximus die. The rest of his crew range from the sublime -- Czar Nickolai the Mad, a summoner who brought Urthrax into the realm -- to the ridiculous: Murray the Miser, a grubby gatekeeper who let Arech's henchmen into Maximus' castle.
What made King's Bounty different from Might & Magic or Ultima was the fact that your character was, almost literally, nothing. A picture on your status screen (one for each of the four classes: Knight, Paladin, Barbarian, and Sorceress), perhaps the ability to cast spells in battle, a couple of numbers, and a rank based on how many villains had been captured. The hero could not directly do anything in battle, leaving it up entirely to his armies.
The armies themselves could be quite impressive -- if the hero was able to lead them. One of the few stats that really affected gameplay was leadership; if the total hit points of one army exceeded that score, it would go out of control and attack randomly. Ghosts were especially prone to this, as any unit they killed joined them. A new character could not hope to control more than about eight mid-strength units; a seasoned general might have a dozen dragons, the most powerful creature around, in his armies.
In contrast to other RPGs of the time, even creatures and monsters traditionally seen as evil could be persuaded to join the hero in his quest. Orcs, vampires, zombies, giants, trolls -- all of these were hanging around, waiting for a general with a goal and money.
The biggest question is, of course: Is it fun?
Yes. It's nowhere near as polished as it could be now, of course, and the graphics are what you'd expect; but it's still a blast. Replay value is actually quite high; while the map doesn't change, the locations are randomized at the beginning of every game. It is, as you might expect, out of print. Sorry.