A lot of stories in Norse mythology deal with how different parts of the mythological world – beings, magical objects, landscapes, buildings – came to be. "The Walling of Asgard" is one of these stories. It gives an account of how Asgard gained its enormous protective wall and how Odin got his magical eight-legged steed, Sleipnir.
Like many of the legends we know about the gods of Asgard, this one is recorded in Snorri Sturluson's 13th-century Prose Edda in the Gylfaginning, or Tricking of Gylfi. King Gylfi attempts to travel to the land of the gods, but instead ends up in a mysterious in-between land where he must engage in a wisdom-contest, asking questions about the Norse cosmos and mythology. The story describing the walling of Asgard is the tale a character named High tells in response to Gylfi's question, "Who owns that horse Sleipnir, and what is to be said of him?" (Prose Edda, Gylfaginning, Chapter 42, p. 55).
It turns out there's quite a lot to be said about Sleipnir. For one thing, he's the love child of the amazingly strong stallion Svadilfari and the trickster-god Loki. Loki is absolutely infamous for producing mutant, monstrous children. With his giantess wife, Angrboda, Loki spawns 1) an enormous sea-serpent; 2) a fierce, world-swallowing wolf; and 3) the ruler of the Underworld. So, it's not surprising that Sleipnir's no ordinary horse. He's got eight legs, and these seem to make him faster than any other horse. Also, maybe because he's the half-brother of its ruler, he's the only horse who can carry his rider to the Underworld.
In a popular 13th-century Icelandic saga (sort of like the Viking version of a medieval romance) the trickster-hero Gestumblindi poses the following riddle:
Who are the twain
that on ten feet run?
three eyes they have
but only one tail.
(From "Heiðreks gátur," Hervarar saga ok Heiðreksin Old
The answer, of course, is the one-eyed god, Odin, riding on Sleipnir the eight-legged horse. The fact that Sleipnir was the subject of a riddle in a popular saga suggests that everybody was familiar with Odin's horse. The archaeological record supports this conclusion: two 8th-century memorial stones from Gotland, Sweden depict an eight-legged horse carrying a rider. In one, a Valkyrie greets the rider with a cup, suggesting that Sleipnir has carried him to the world of the dead. Popular legend in Iceland also attributes the horseshoe-shaped canyon Asbyrgi to the imprint of Sleipnir's hoof.
With Sleipnir such a well-known mythical figure, possessing so many mysterious powers (and so many limbs), is it any wonder that the story of his origin is an elaborate tale of intrigue, magic, and mayhem?