ある国の王様が亡くなった。王子は幼かったため摂政がたてられた。
摂政は「氷雪婦人」の異名を持つ敏腕だが底が知れない女。彼女は大昔に途絶えた王家の成人儀式「試練の旅」を復活させ、王子を国境近くにある魔獣の住処「死の谷」に向かわせる。
「試練の旅」は近衛や護衛に冒険者を随行させることを禁じており、ひとりきりで旅する習わしである。しかし、摂政をつけるほどに幼い王子に何ができるのか?
死を覚悟する王子。旅立ちの前日の晩に現れたのは?
「だれ?」
「だれって、猫だけど……」
カーテンの陰から出てきた猫がしゃべった。
「明日からの旅に家来は連れていけない。冒険者もダメ、執事もダメなら、メイドもダメ。だけど、規約には想定外もある。キミを助けてくれる人を連れていく方法が隠されている。まずはボクを連れていきなよ」
「そっか、ペットの同伴は禁止されてなかった!でも、猫なんて何の役にたつのかな」
「違うなあ。そうじゃない。ボクをキミのお嫁さんにしなよ。王妃にさ。その条件ならキミにいろいろ知恵を授けてあげる」