The book begins during the construction of Redwall Abbey, when a roving female hedgehog named Trimp visits the abbey and sings a song to help the workers lifting a beam. Martin the Warrior recognises his father, Luke the Warrior, mentioned in the lyrics and asks Trimp more about him. He decides to go on a quest to learn more about his father. Martin, Gonff the Mousethief, Dinny, and Trimp befriend an orphaned woodlander squirrel named Chugger, the bird Krar Woodwatcher, as well as two brother otters, Folgrim (who is very close to becoming feral, having filed his teeth to points, and even eating vermin after he kills them) and his older brother Tungro. When they reach the northlands, Martin meets his father's friends: the old mouse, Vurg, and Beauclair Fethringsol Cosfortingham, an exuberant old hare. They show him a book titled "In the Wake of the Red Ship", an account of Luke's life.