宿敵ラビックを倒し、ログレス七カ国に平和をもたらしたアーサー。だが海の向こうでは、悪逆非道なザイキングによって多くの人々が苦しめられていた。アーサーは身分を隠してザイキングを退治する旅に出る。だが、事情を探ろうと訪ねたグック船長は、ザイキングの襲撃に遭って殺されていた。ザイキングには、ボスマンとピートも追われていた。二人を助けたアーサーは、グック船長の隠した宝を一緒に探そうともちかける。
道に迷って腹ペコのボスたちは、牧場で知り合ったマリアに誘われ、宿場町の食堂に転がり込む。ところが、山賊のビッグベアーによって食事を邪魔されてしまう。怒ったボスも力でねじ伏せられ、マリアを連れ去られてしまう。アーサーはマリアを救うため、わざとビッグベアーの仲間になるが、再び宿場町が襲われることを知って手紙で危険を伝える。手紙を受け取ったボスは、力を合わせてビッグベアーを倒そうと町の人々に協力を頼むのだが…。
逃げ出したサンデーを追いかけて、豪華な館へたどり着いたアーサーたち。だが、その館はすでに北の魔王の配下によって占拠されていた。魔王の配下・バスラは、館に隠された金貨を狙っていた。ソニア姫を裏の塔に閉じ込め、隠し場所を言わなければ捕らえた召使たちを殺すと脅していたのだ。一方、バスラに監禁されたアーサーは、抜け穴を通って脱出に成功。しかし、怒ったバスラがボスたちを納屋へ閉じ込め、非情にも火を放った!
アーサーたちが立ち寄ったのはまるで天国のように美しい町。しかし、その町は保安官ゴードンによって牛耳られていた。ゴードンに言いがかりをつけられたボスは、腹を立てて大暴れ。それを見た町長がボスを気に入り、新しい保安官になってくれと持ちかけてくる。報酬の砂金を見せられて乗り気になったボスはふたつ返事で引き受けるが、うますぎる話に疑いをもったアーサーとピートは町の様子を調べ、ゴードンたちの恐ろしい企みに気付く。
水汲みに出たピートが戻らない。探しに出たアーサーとボスは納屋に監禁されていたピートを発見。助け出すものの、武器を持った人々に囲まれてしまう。彼らは北の魔王の配下・クロノスに子供を差し出せと脅され、ピートを身代わりにしようとしていたのだ。クロノスは子供たちはザイキングの兵士にするつもりらしい。さらわれたピートの奪還に向かうボス。ところが毒味のワインに眠り薬を盛られ、絞首刑を宣告されてしまう!
砂漠越えの途中でピートが体調を崩してしまう。困りはてたアーサーたちの前に美しい城が現れる。そこは女だけが暮らす城だが、病人を休ませるためなら男にも特別に滞在が許可される。意識を取り戻したピートは、アーサーたちを探しに行く途中、リリーという美少女に出会う。一方、熱烈な歓迎を受けたボスマンは、浮かれて城に留まり続けると言い出す。歓待の女たちの中にリリーの姿を見つけたピートはショックを受け、ボスと大ゲンカを始めてしまう。
ハンス少年は泣き虫の罰として納屋に閉じ込められてしまうが、そのおかげでザイキングの襲撃からただ一人難を逃れた。荒らされた村に入ってきたアーサーたちは、保護したハンスに事情を尋ねる。どうやらザイキングは、空飛ぶボートに乗って攻撃してきたらしい。ボスとピートは空飛ぶボートを盗み出そうとするが失敗。アーサーは怯えるハンスを叱咤する。両親や友達を救えるのはハンスだけであり、みんなのために勇気を出せと。
ボスたちは昼寝の途中に見かけた海賊船の後を追い、北の魔王の砦を突きとめる。ついに宝物が手にはいると大喜びのボスだが、砦には様々な仕掛けがほどこされていて、容易には近づけない。偵察に出たアーサーは、アンナという女性から、ザイキングに連れ去られた兄のエルテスを助け出してほしいと頼まれる。火薬の研究をしていたエルテスは、騙されて戦いに使うための火薬を作らされていたらしい。アンナのため張り切るボスだったが…。
ボスとの賭けに勝って金貨を貰ったピートは、市場でパンを買おうとしてその値段にビックリ。何とパンひとつが金貨一枚だというのだ。その原因は白馬の王子に食料を奪われたから!? 腹を立てたボスが反論。うっかり王子の親友だと言ってしまったため、城に連行されて死刑を宣告されてしまう。アーサーは自分が犯人を捕らえると名乗りを上げるが、伯爵はわざとピートとボスに捜査を命令し、アーサーは人質として牢に繋いでしまう。
突如現われたザイキングの忍者に、ボスとピートが捕まってしまう。忍者の頭領・ラージは、二人をエサに白馬の王子をおびき出し、正体を暴こうと試みる。ボスたちの救出へ向かう途中、アーサーは崖から滑り落ちて怯えるポニーを見つける。アーサーはポニーを助けて仲間のもとへ戻してやるが、その姿を忍者一味に見られてしまった。忍者軍団の卑劣な罠が、白馬の王子を待ち受ける。苦戦するアーサーの前に現れたのは…?
北の魔王の配下・ワルダンは、虎視眈々とサクソン城を狙っていた。城に国賓のギネビア姫が訪れていることを知ると、ワルダンは誘拐して身代金を取ることを計画。ピートとボスがサクソン城へ報せに走るが、疲労のあまり動けなくなってしまう。このままでは間に合わない。ピートはサンデーが飛ぶ姿にヒントを得て、布切れで人力飛行機を作って空から城を目指す。ところがザイキング兵の攻撃で城内は大混乱、ギネビア姫はワルダンの手に落ちてしまう!
アーサーたちは森の中で熊に襲われていたアリスという少女を助け、家まで送り届ける。母親からお礼をしたいと言われて一晩やっかいになるが、その家は女忍者が用意した死の家だった。アリスもまた、幼い頃より訓練された女忍者だったのだ。だが、アリスは自分を救ってくれたアーサーを殺すことができず、見逃してほしいとベラに懇願する。非情なベラはそれを許さず、アーサーを恐ろしい仕掛が施された部屋に閉じ込めてしまう!
川の近くに差しかかったアーサーたちは、茂みの中でザイキング兵の死体を発見、近くの村でザイキングと村人たちが戦っていることを知る。勇敢に戦う村人たちの中に、ローラという女性がいた。髪を切って男装し、殺された父の仇を討とうと、先頭に立って剣を振るっていたのだ。ボスとピートはザイキング軍のノロシを発見。アーサーは女と子供を洞穴に隠すと、ピートに石投げ器を作らせ、村人たちと共に敵を迎え撃つ!
ザイキングがいかずちの壺を奪う現場を目撃したギネビア姫は、アーサーの命に危機が迫っていることを知り、ランスロットを使いに走らせる。そのアーサーは、岩場で怪我をしたボスのために、休ませてもらおうと通りがかった館を訪ねていた。だが、その館にはザイキングの罠が仕掛けられていた。鉄柵の中に閉じ込められてしまったアーサーは、いかずちの壺から流れる電気のために柵に触れることさえできず、逃げ場を失ったまま火矢を射かけられる!
白馬の王子がアーサーではないかと疑うラビック王は、魔女メデッサに助力を乞う。アーサーへの復讐に燃えるメデッサは、狼族のギルの力を借りて王子の正体を暴こうと企む。一方、森の中でザイキングが城を襲う現場に遭遇したアーサーは、白馬の王子になって敵を撃退。ところがその城には、いるはずのないギネビア姫がいた。大事な話があると広間へ案内されるが、どうも様子がおかしい。目の前にいるのは果たして本物のギネビア姫なのか…?
火を吐く竜の噂を聞きつけたボスは、退治して有名になろうと湖へやって来る。だがその竜は、北の魔王によって作られた精巧なカラクリだった。ボスの功名心を利用して、白馬の王子を誘き出す作戦だったのだ。一行は竜に襲われたロコという少年から話を聞き、彼がたった一人で仇を討とうとしていることを知る。味方になることを約束するアーサーたち。その夜、船小屋で眠る一行にザイキング兵が忍び寄る。
アーサーたちは神父を手伝って、マリア像を町に届けることになった。そこにザイキング兵が襲いかかってくるが、謎めいた黒馬の騎士によって救われる。黒馬の騎士はワルダンの弟で、兄の仇を討つために白馬の騎士を捜していた。彼はボスたちが窮地に陥れば白馬の王子が現れると知り、わざとザイキングを呼び寄せる。そして、海賊船の待ち伏せを受けたボスたちを救うため駆けつけた白馬の王子に、一対一の戦いを挑んでくる!
雨宿りのため古い館に入り込んだアーサーたちは、魔よけのしるしが描かれた不思議な絵の中へ吸い込まれ、絵の中で妖精ジニーと出会う。ジニーからガーゴイルに盗まれた魔法の杖を取り戻してほしいと頼まれ、ボスとピートが透明になる油を塗って盗み返そうとするが、調子に乗ってイタズラしたせいで見つかってしまう。怒ったガーゴイル二人を釜茹でにしようとする。アーサーは二人を救うため、元の世界へ戻してほしいとジニーに頼むが…。
大きな川に足止めされ、野宿を決めたアーサーたち。アーサーは川辺で、ボスの銛に刺されて苦しんでいた人魚のレナを助ける。レナはもともと人間の女性だったが、川に棲む恐ろしい魔女に恋人を殺された挙げ句に姿を変えられ、生き血をすするための人間を捕まえることに協力させられていたのだ。ギアナからアーサーを連れてくるように命令されたレナは、恋人に生き写しのアーサーを殺すことができず、身代わりにボスを水の中へと誘い込む。
北の魔王の城へと急ぐアーサーたちは、近道をしようと山越えを計画する。しかし見知らぬ老人から、山を越えようとする者は雪女によって命を奪われると忠告を受ける。だが今は夏。雪女など出るわけがないと山越えを決行するが、途中でひどい吹雪にみまわれてピートの姿を見失ってしまう。必死に行方を探すボスとアーサーは、無事に保護されていたピートを迎えにいくが、その家の女主人・アシュラに眠り薬を盛られてしまう。彼女こそ雪女だったのだ!
ついにザイキングの本拠地を発見したアーサーたちは、サンデーの案内で財宝のありかを突き止める。念願のお宝を見つけて大喜びのボスとピート。しかも金貨の山で見つけた壺にはグック船長からの手紙が託されていた…。ラビック王はどんな魔物をも永久に封じ込めることができる“ウルドの壺”が持ち去られたことを知ると、もはや他人にはまかせておけないと自ら鉄の馬で出陣。アーサーたちに絶体絶命の危機がせまる!
北の魔王の正体はラビック王だった。キャメロットの王子であることを明かしたアーサーは、改めてボスとピートに力を貸してくれるよう頼む。壊れた海賊船を修理し、ボスが船長、ピートが大砲係となって北の魔王の城へ乗り込むが、メデッサの魔力により船は破壊され不時着を余儀なくされてしまう。魔女メデッサの霊魂を倒すには、エクスカリバーで立ち向かい、再び甦ることのないようウルドの壺に封印するしかない。今、最後の戦いが始まる!
(C)東映アニメーション