The Valhalla Express is described as a Viking boat, implying that an unknown Viking tribe built it, but came into the possession of the Romans located at Fort Sinister.
Hiccup, Fishlegs, and Camicazi are prisoners of the Romans and are kept alive until Saturn's Day Saturday, where they are to perform in a gladiatorial event in the amphitheater for the Romans' enjoyment. The Viking children are surprised when they are led to an underground area with a boat called The Valhalla Express. They are loaded aboard and the area is flooded with water and they float into the arena. Sharkworms are also released into the arena for them to battle. Hiccup gets into a barrel and is thrown overboard to distract the Sharkworms and set his plan with Ziggerastica in motion. When it appears the Sharkworms have done him in, he burst from the water and flies around the area and pretends to be the God Thor. In actuality, a multitude of tiny nanodragons are flying him around. The Fat Consul acquiesces and vows to leave the Barbaric Archipelago. With the arena in an uproar, Hiccup returns to The Valhalla Express are the gang attempts to sail away. However, the Thin Prefect figures out what had happened and orders the porticullis to be lowered, which cuts the The Valhalla Express in two. The children cling to the gate and search for another way out.
The Romans named The Valhalla Express, possibly as a joke because those aboard where expected to be going straight to Valhalla once they got into the arena.