The player characters receive a letter from a dying man who informs them that, during a celebration of your defeat of the evil wizard Mangar, his true master—the Mad God Tarjan—arrived and unleashed foul creatures that destroyed the town of Skara Brae. The box cover states it thus:
Skara Brae is in ruins. Roscoe's Energy Emporium stands vacant. The Equipment Shoppe went under so quickly Garth was crushed. Your Bard hasn't stopped whimpering since he realized all the taverns were closed.... Someone—or some thing—has sealed the city's fate with an evil so vast, so unspeakable, that a host of Paladins and an army of Archmages are out-matched. Hard times call for subtlety. Smaller is better. Sneakier is better. What the world needs now is a thief. The Thief of Fate.
The game begins in a refugee camp outside the ruined Skara Brae, which replaces the now-destroyed adventurer's guild from the previous games. Besides the city ruins, the wilderness features a temple for healing, a tavern, and a number of special locations from where the party will embark on missions to other worlds over the course of their quest.
Skara Brae was scaled down considerably. The ruins are 16x16 map tiles instead of the city's 30x30 layout from The Bard's Tale I, though its layout remains recognizable. In the ruins of the Review Board, an old man—the sole survivor—directs the party to first kill one Brilhasti ap Tarj, a servant of the mad god Tarjan, in the "Mad God" dungeon below Skara Brae, a startup quest for the characters to attain power, which can be ignored if powerful characters were carried over from previous games. Next, the old man orders the party to retrieve artifacts from several other worlds and also teaches the group the chronomancer spells to be used at certain points in the wilderness to travel to these parallel dimensions and back:
Arboria (from Twilight Copse): Pleasant elf realm including the city of Ciera Brannia. They have to bring back the hero Valarian or get Valarian's Bow and the Arrows of Life. It turns out Valarian is long since dead and buried in a sacred grove with the items. The king will only allow the party to enter the grove if they first kill the local villain Tslotha Garnath with the Nightspear that can be obtained from Valarian's Tower. In Arboria, the party meets the warrior Hawkslayer for the first time, though he recalls meeting them before (a hint at the fact that the party is travelling not only between dimensions but also across time in their quest).
Gelidia (from Cold Peak): The party is next tasked to bring Lanatir or, if they cannot convince him to come, Lanatir's Sphere and the Wand of Power back from this dimension of magic. Gelidia turns out to be an icy wasteland with a great ice keep. In a nearby hut, a diary is found with the frozen corpse of a half-elf later identified as Alendar, who is suggested to be dead for a thousand years already. The diary relates how the garrison, lacking a hero like Hawkslayer this time, fared poorly against attackers who killed the god Lanatir. Lanatir was buried in his keep by his remaining followers, who then sealed it with powerful magic. Alendar, the last survivor, finally cast a spell of eternal winter upon the land to vanquish the invaders and then died in the cold himself.