トリスタン（チャーリー・コックス）の住む村のそばには、外の世界との境界となっている壁がある。外の世界は謎につつまれ、壁を越えることは禁じられていた。ある夜、トリスタンは、壁の向こうに一筋の流れ星が落ちていくのを見る。片思いの少女へのプレゼントとして、流れ星を取ってこようと決めたトリスタンは、父親に、壁を越えたいと打ち明ける。そんなトリスタンに、父は、かつて自らも壁の向こう側へ足を踏み入れたことを告げる。そして、壁の向こうの魔法の国・ストームホールドで出会った女性こそが、トリスタンの母であることも。トリスタンは、父から、使えばすぐに母に会えるというロウソクを手渡される。ロウソクに火を灯すと、トリスタンは時空を越え、ストームホールドへ。そこには、ルビーのペンダントをつけた一人の女性の姿があった。女性は、トリスタンの母ではなく、イヴェイン（クレア・デインズ）と名乗る。トリスタンは、彼女こそが、女性へと姿を変えた流れ星だと確信し、村へ連れ帰ろうとするが、イヴェインは、トリスタンの元を去ってしまう。一方、ストームホールド内では、王の死により、七人の王子達による王位争奪戦が繰り広げられていた。王位を継ぐ者が持つルビーのペンダントが、イヴェインの手元にあると知った王子達は、イヴェインの追跡を開始する。更に、永遠の若さを手に入れるため、流れ星の心臓を手に入れようとする魔女ラミア（ミシェル・ファイファー）までもが現れて、イヴェインの前に罠を仕掛ける。