Ultima Underworld II: Labyrinth of Worlds takes place one year after the events of Ultima VII: The Black Gate. To celebrate the defeat of the Guardian, Lord British invites the Avatar and his companions to his castle. However, in the night of the feast the Guardian attacks again, encasing the castle in a giant gem of blackrock. Deep in the sewers of the castle, another blackrock gem is found, created as an aftereffect of the attack. This gem is a teleporter to other worlds controlled by the Guardian. Now the Avatar must travel to these worlds in order to free the castle from the Guardian's spell.

This sequel to Ultima Underworld plays almost exactly as the original, with its 3D world, action-oriented combat, magic system and multiple-choice conversations. The player creates the character of Avatar, choosing gender, class, and initial skills. These range from weapon proficiencies to social abilities such as diplomacy and bartering. Some of the skills can be increased during the course of the game by visiting trainers. After having accumulated a sufficient amount of experience points, the Avatar levels up, and his hit points and mana are increased. Like its predecessor, the game features an interactive world: many objects can be manipulated and physically moved.

The game's storyline is more connected to the main Ultima series than that of its predecessor, and the game world is larger and has more variety: besides the usual castles and dungeons there are such diverse locations as an ice world, an alien place called Talorus and the enigmatic Ethereal Void. Graphics and sound have also been improved: the size of the viewing window has been increased, there are new monster graphics and the game now features digitized sound effects.