The sequel takes place after the first game and features the original three characters plus two new playable characters, Fang the wolf and Scorch the dragon.

After escaping from Tomator in The Lost Vikings, Eric, Olaf, and Baleog have lived joyous and fruitful Vikings lives. Then one day, after returning home from a fishing trip, the Vikings get captured by Tomator again. Tomator then calls upon a robotic guard to send them into the Arena, which unfortunately falls short when a system failure happens. During the blackout, the three Vikings dismantle the robot piece by piece and wear its parts on their body, thus granting them new abilities. The three Vikings are then sent through time once again when Olaf pulls the switch on the time machine that says Do Not Touch, which he mistakes for Donuts. Equipped with the new robotic gear from the robot guard they destroyed earlier, Eric, Olaf, and Baleog must fight their way through time once again in order to find their way back home. Along the way, they befriend a wolf named Fang (whom they continuously humorously mistake for a different animal) and a dragon named Scorch.