人間の勇者によって、魔王トールが倒された。新たな魔王を選ぶべく、魔族たちは競技会を開催するが、そこには敵である人間の勇者、ヘルクの姿があった。帝国四天王の一人、赤のヴァミリオはその存在を警戒し、あの手この手で排除しようと目論むが、ことごとく失敗に終わる。「人間が憎い」、「人間を滅ぼそう」と宣言するヘルク。人間界に潜入している諜報員・アスタによってもたらされた彼の意外な正体とは……!?

大会の副責任者であるホンのせこい罠をものともせず、順当に勝ち進み、観客の絶大な人気を得たヘルク。彼は、大会終盤のレース対決へと駒を進めていた。しかし、ここでもホンの姑息な妨害工作により、圧倒的不利な状況に追い込まれてしまう。無情にもスタートの大砲が響き渡る中、大観衆の声援を受けたヘルクは、快進撃を続けることができるのか?

レース対決を制し、決勝戦へと勝ち進んだヘルク。決勝の舞台は、翼の兵士たちの襲来により陥落したウルム城。優勝者は翼の兵士たちのリーダーを倒したものとするという。ヘルクたちは正体を隠したヴァミリオと共にウルム城へ向けて旅立つが、決勝進出者たちに緊張感はない……。そんな中、圧倒的な強さを見せつけるヘルクに、ヴァミリオは益々警戒心を強めていく。

翼の兵士たちのリーダーであるエディル。魔王の座を勝ち取るべくヒュラが仕掛けるが、一瞬で間合いを詰めたエディルに右腕を落されてしまった。「人間たちは翼を持った勇者へと覚醒した」と語るエディル。エディルへの攻撃をかばうヘルクを見て、ヴァミリオは敵だと判ずる。が、直後に床が崩れ全員地下空間へと落ちてしまい……。

謎のゲートの力で、未知の孤島に飛ばされてしまった、ヴァミリオとヘルク。浜辺で目を覚ましたヴァミリオは、島の奥へと進み、そこでフワフワの生き物と遭遇する。色々と規格外なヘルクによって助けられたヴァミリオは、彼が敵なのか味方なのか迷い始めていた。一方、ヴァミリオ行方不明の知らせを受けたアズドラは、捜索隊を編成し、手がかりを求めて人探しの秘術を行うが……。

島の住民の歓迎を受け、穏やかな日々を過ごすヘルクとヴァミリオ。ヴァミリオは、少しずつヘルクへの警戒心が薄れていく。「かつての仲間と戦えるのか？」……ヴァミリオの問いかけに「同じ人間である俺が終わらせたい」と決意を語るヘルク。一方、ウルム城に残されたヒュラたちは、圧倒的な数で押し寄せる翼の兵士たちに追い詰められていた。

ホンとイスタの案内で、何とかウルム城から脱出したヒュラたち。再び敵に囲まれるも、援軍として現れたアズドラの圧倒的な強さによって、翼の兵士たちは一瞬で拘束される。形勢が逆転したにも拘わらず、頑なに魔族を悪と決めつけ強気な姿勢を崩さないゼルジオンたち。一方、ゼルジオンの言葉から翼の兵士たちの実態を知ったアズドラは、ある作戦の実行を決意する。

戦闘と死を繰り返し経験する事で成長する翼の兵士たちが、帝国の脅威になると考えるアズドラ。その元凶である人間の王を倒すために、ウルム城の防衛と、トール城の奪還を決行する。一方、大陸への行き方を知っているという魔女と会えないまま、のんびりと過ごすヘルクとヴァミリオ。魔女が村へ降りてきたという情報を受けて彼女の住む山へと向かうが、ヴァミリオはそこである忠告を受ける。

謎の村の住人たちに見送られ、コッソリ乗り込んでいたピウイと共に、島を旅立ったヘルクたち。順調な船出に思われたが、魔物に追われて霧の海域を超えると、目の前には巨大な渦が……！そんな中、ヘルクは再び現れた魔物によって海の中へ引き込まれてしまう。戻らないヘルクを待つヴァミリオだったが、船は大陸に辿り着いてしまい……!?

エリーユの街で、トースマン族と戦うヘルクたち。強さに執着したトースマン王は、謎の力で暴走してしまう。トースマン王との戦いを終えたヘルクたちは、帝国へと向かう為の地図を求めて、次の町へと旅立つ。砂漠に囲まれた行商の町で見つけた高額な地図を買うために、優勝賞金が出る料理大会に参加するヘルクたち。だが、そこには料理に自信がある凄腕たちが集まってしまい……。

凄腕の料理人が参加する料理大会を制したヘルクたちは、獲得した賞金を元に帝国への地図を手に入れた。北西の“滅びた二つの国”を目指すことにするヘルクたち。一方、それを聞いた地図屋の店主は、遭遇すれば生きて帰れないという“闇の戦士“が出るので、死にたくなければ迂回しろと忠告する。時間が惜しいヘルクたちは、滅びた二つの国へまっすぐ向かう。だが、風化した街並みを歩いていると、不気味な気配が背後に迫り……!?

闇の戦士・アウギスとの戦いで、暴走したヘルクの力に戦慄するヴァミリオ。ヘルクが危険な存在だという魔女からの忠告が頭を過る。一方、トール城の奪還に成功した帝国軍は、諜報員・アスタの情報を元に、度重なる人間の襲来を強固な守りで撃退していた。「勇者は何度でも蘇る」と話す翼の兵士たち。彼らは戦う度に成長を遂げ、着実に強くなっていく……。

幼い頃に魔物によって両親を失った兄ヘルクと弟クレス。王都のスラム街にたどり着くも、暮らしは貧しくクレスが重病になってしまう。弟の救済を叫ぶヘルクに街の人々は冷たかった。そんな彼らに手を差し伸べるラファエド。回復したクレスは民のために強くなる事を誓う。やがて勇者へと成長し討伐の旅に出る弟に再会を誓うヘルクだったが……。

国境付近の魔物討伐部隊の一員として山岳地帯に赴くヘルク。新世界生物と渡り合える己の力を自覚し、魔物に襲われたエディルの領地を守るべく走る。その道中、傭兵アリシアとその部下達に出会ったヘルクは、仲間というものを知る。一方、魔王を倒したにもかかわらず、新たな魔物が王都に攻めてくる事態が発生したことから、民衆たちはクレスを罵し始めて……。

たどり着いたトール城内でただならぬ気配を感じるヘルク。人間と友好な関係を築きたいという帝国四天王アズドラ。王都へ戻ったヘルクは彼を信じ、その言葉を民衆に伝えようとする。だが、長年積もった魔族への憎悪は容易には覆らない。徐々に戦いの道へと進んでいく民衆に、一人悩むヘルク。そんな彼の元に、クレスの親友・ゼルジオンが訪れる。

ゼルジオンからもたらされた恐るべき王国の計画。それを阻止し、クレスを救うために王城へ潜入するヘルク達。そんな彼らを人間の王の言術によって操られたクレスが襲うものの、アリシアの持つ剣『勇者殺し』がクレスの凶刃を食い止める。クレスを奪還し、作戦は成功したかに見えた。だが、真の実力を出したミカロスがアリシアを倒し、『勇者殺し』でヘルクを襲い……

窮地のヘルクを救ったのは自我を取り戻したクレスだった。しかし、再び王の言術がクレスを襲う。兄を守るためにクレスが選んだその結末にヘルクは悲しみ、怒りを暴走させる。乱戦の中で意識を失うヘルク。昏倒の果て、ふと洞窟で気づいたヘルクは自身と仲間達の境遇を知らされ愕然となる。そしてヘルクはあることを決意する。

走るヘルクの前に立ちはだかる賞金稼ぎや兵士達。大軍をことごとく打ち倒してひたすらに王都へ向かうヘルク。そこで見たのは処刑場に引き出されたアリシアの変わり果てた姿だった。人々の仕打ちとその醜さに怒るヘルクだったが、アリシアは傷つきながらも彼を優しく気遣う。やがて二人の再会を祝うかのように雪が舞い落ち始めるが—……。

恐るべき人間の覚醒、友たちとの別れ、悲しき決意……。ヘルクの話を聞いたヴァミリオはあらためて本来の身分を明かし共に立ち向かうことを誓う。二人は荒野を走る機関車での旅を経て、怪物退治で沸き返る街で捜索隊員ハルピィと接触。彼女に託されたアズドラの書簡を読み、ヴァミリオは自分達の進むべき道を決める。

更なるレベルアップを求めトール城に殺到する翼の兵士達。死ぬ度に強くなる彼等に打つ手はあるのか。一方その頃、人間側の情報を探るべく王都に忍び込んでいたアスタは逃走の果てにとある一画に足を踏み入れる。そこで出会ったのは覚醒していない無垢なる人間の少女、シャルアミだった。不思議な存在感を持つ彼女はアスタをお茶に誘う。

ゼルジオン率いる翼の兵士たちに襲撃されるシン魔王城。人間と魔族、互いに一歩も引かない攻撃の応酬が繰り広げられる中、お面をつけたアズドラが伏兵を率いて現れる。一方、結界石を狙うミカロスは、アズドラの不在を見越してトール城に侵入する。城を守る魔族からの攻撃をはねのけ、地下へと向かうミカロス。だが、そこで待つ一人の男に彼は驚愕する。

トール城で戦うヒュラとエディル。刃を交わす中で二人には奇妙な感情が芽生え始める。一方、結界石を目前にして現れたアズドラに、かつての因縁を明かすミカロス。新世界の力を用いて攻撃を仕掛けてくるミカロスに、アズドラはある決意をする。その頃、人間の王城ではアスタがシャルアミを連れて、城からの脱出を図っていた。仲を深めつつ、逃走する二人。だが、その途中彼らは“王の間”に行き着いてしまう……。

魔族の前線基地を襲うラファエドの軍。そこへ現れるヴァミリオとヘルク。抗う事を止めろと諭すラファエドに、「人間を滅ぼす」とあらためてヘルクは宣言する。ラファエドは、ヴァミリオがヘルクの新たな心の支えと見抜き彼女を攻めるが、圧倒的な魔力で応戦するヴァミリオ。一進一退の攻防の中、何者かがヘルクに一本の矢を放つ。その正体とは……。