The follow-up to the original Lords of Midnight game uses a similar game system to its predecessor, but the story is now much more complex. Luxor the Moonprince's son Morkin has been kidnapped by Shareth, daughter of Doomdark, the evil ruler deposed in the first game. The player initially takes control of Luxor, Rothron the Wise, and Morkin's lover Tarithel the Fey, although many more characters can be recruited as the game progresses, as they aim to banish Shareth and rescue Morkin. Shareth has brainwashed him, so he must also be turned back to Luxor's side.

The game is effectively turn-based; your characters move by day (with a limited amount of movement possible, with each move in one of the 8 compass directions) and Shareth's by night. You will find plains, mountains, forests, underground tunnels and mysterious temples on your journey. A dark mist follows much of the area, which causes your characters to deteriorate in mood and thus become less effective.

The characters are now split into five distinct tribes - Giant, Dwarf, Fey, Icemark and Barbarians, and recruiting new characters into your party isn't automatic - factors such as the game situation can make some refuse to join, turn on members of other races, or defect (as the Utarg did in the first game).

There are several different objectives and possible outcomes to the game. Bringing Morkin back to the Gates of Varenorn is the most basic one, but many other characters ought to be saved, Shareth can be killed completely (with practice!), and there are many Crowns of Icemark to be retrieved. As in the first game, control of the full party only remains while Luxor is alive - his death means total defeat.

Morkin, devastated after destroying the Ice Crown, believes the war is lost and Midnight is doomed. Aimlessly wandering through a dark forest. Tarithel, daughter of the Lord of Dreams, finds him and takes him to her home, the Citadel of Dreams. There Morkin learns that the war is won. Doomdark is defeated, and Morkin’s father, Luxor, is alive. Morkin explains that he destroyed the Ice Crown but thought it was too late. The bond between Morkin and Tarithel deepens in the following days.

Meanwhile, Shareth, the Heartstealer and Empress of the Icemark, erupts in rage upon learning that her father, Doomdark, has been slain by Luxor. Enraged that her revenge has been stolen, she summons a great storm to strike south against Luxor and Midnight. Giants and Dwarves prepare for battle, while the Fey Lords of Imorthorn, sensing the storm’s threat, send a white falcon with a warning to the Citadel of Dreams.