北方王国は南方王国との戦で滅び、そして今また、もうひとつの滅びを迎えようとしていた。北方王国最後の姫、強大な魔力をそなえていたと語られる氷のイザモルドがかけた呪いが、年ごとに冬を延ばし、春を遠ざけていたのだ。すべて氷りつけ——北の大地は人の住める土地ではなくなっていた。
その夜、国境近くの小さな酒場に逗留していた南方人のうたびとアストラは、異様な客を迎えた。彼はアストラを探して来たのだと告げた。氷姫の常春の庭への案内役として。
東からの旅人はシリエンと名のり、この世には自分の知らぬこととてないとうそぶいた。彼を襲おうとした異形は、シリエンを呼んだ——妖魔の王、と。
たしかにアストラは、氷姫の庭を見たことがあった。失われた北方の音楽をもっと知りたい一心で故国を出奔した彼は、なんの偶然か氷姫のもとへ至り、かの美姫と言葉をかわしもしたのだ。凍りついた世界にあって、絢爛と花が咲き匂う庭園に佇み、孤独を嘆いた彼女の姿を、忘れたことはなかった。
断りきれず、アストラはこの奇妙な相手と同道することを決めた。道など覚えていないも同然の彼だったが、いわれもなく辿り着ける場所ではない。妖魔の王は、若きうたびとと魔法の庭のあいだにある、未だ見えない縁をあてにしているのだった。
酒場を出たかれらがまず向かったのは、サーライと呼ばれる場所だった。ここの魔女は力が強く、今のところは氷姫の呪いに抗して自身の領土をたもっているという。魔女エイーシャの命に応じて姿をあらわした魔物は、王国随一のうたびとと褒めそやされたアストラすら嫉妬するような美声で、彼が求める北方歌謡を披露したのだが——。