The Sea of Trolls is set in Anglo-Saxon England, Scandinavia, and the mythical realm of Jotunheim. Jack Crookleg, the main character of the book, is being trained by a famous skald named Dragon Tongue, when he and his younger sister, Lucy, are captured by Viking raiders. The pair are to be sold as slaves to "Picts" as soon as they reach land. On board the Viking ship Jack meets and ultimately befriends Thorgil, a young would-be berserker, and Olaf, the leader of the raiders, along with Boldheart, the crow. The two captives are spared because Jack is a bard and because Lucy is to be given to the queen, a half-troll named Frith.
When they arrive at the court nothing goes as planned. Jack is sentenced to menial labor and made to clean the barn. There Jack encounters the deadly troll-pig, Golden Bristles, who is to be sacrificed to the goddess, Freya, by being placed in a wooden cart and left to sink in a bog. After singing Olaf One-Brow's praise-song for the Northman's homecoming, Jack inadvertently makes Queen Frith lose her hair. Queen Frith threatens to sacrifice Lucy to the goddess Freya, because Jack set Golden Bristles free. However, Frith allows Jack a chance to save Lucy and their freedom if he can make her hair grow back, which is much more difficult than she makes it sound. Jack goes with Olaf and Thorgil to Jotunheim, land of the Trolls, to seek the mythic Mimir's Well, a well with magical water which gives the drinker knowledge, at the roots of the world tree Yggdrasil. Olaf One-Brow is killed by a "trollbear," a gigantic bear native to Jotunheim. Jack and Thorgil are captured by a dragon, but Bold Heart tricks the dragon and enables Jack and Thorgil to escape. Thorgil slays the baby male dragon but gets some blood on her tongue, allowing her to speak with birds. On the way Jack also visits the queen of the Jotuns, as he needs her consent to continue seeking Mimir's Well. He finds the tree Yggdrasil and Mimir's Well. Both he and Thorgil drink from the well, and Jack saves some for Rune, a skald who teaches Jack poetry. With the knowledge Jack gains from drinking from Mimir's Well, he returns to the land of the Northmen to restore Frith's hair. Upon return, Jack and Lucy are summoned to the court. Jack explains to Queen Frith that she needs to cut off 1/3 of the hair from her troll cats but no more to restore her hair. She doesn't listen and cuts all of the cats' hair off. As a result, Frith's hair grows everywhere not just back on her head. She runs off crazed. Later Olaf's oldest son commands the ship and takes Jack and Lucy back to their village. Jack finds his mother and learns that Dragon Tongue has been crazed ever since Jack and Lucy's kidnapping. He goes to see Dragon Tongue with Bold Heart and Dragon Tongue's heart stops beating. Jack gives Dragon Tongue the remaining mead from Mimir's Well and he comes back to life. Dragon Tongue tells him that he became a crow during the voyage.
