皇帝ハルシャ6世の誕生式典の日。四公爵の一人、アリアバート・タイタニアは辺境の都市国家エウリヤを攻撃するために出撃していた。エウリヤ艦隊に対し、圧倒的多数を誇るアリアバートの艦隊。その勝利は誰の目にも確実なように思われた。だが、別の公爵ジュスラン・タイタニアは、言い知れぬ不安を感じていた…。

敗北を経験したアリアバートに対し、きびしい言葉をあびせるザーリッシュとイドリスの二人。だが、アリアバートの失敗をせめず、敵が無名の若者ファン・ヒューリックに艦隊の指揮をまかせたのかという疑問を指摘するジュスラン。その一方、英雄になったはずのファン・ヒューリックには、意外な運命が待っていた…。

エウリヤを追われたヒューリックは、惑星エーメンタールに逃れていた。だが、タイタニアによる逃亡者ファン・ヒューリックの指名手配の知らせは、エ―メンタールにも届いていた。職を探しに職業安定センターに向かったヒューリックは、四公爵の一人ザーリッシュの弟、アルセス・タイタニアの手の者に捕まってしまうが…。

危うい所でアルセス・タイタニアの屋敷から脱出することができたヒューリック。彼を救い出したのは、リラ・フローレンツたちタイタニアに滅ばされたカサビアンカ公国の生き残りであった。アルセスはヒューリックを捕まえることによって、タイタニア一族の本拠地「天の城（ウラニボルグ）」への帰還を目論んでいた…。

ヴァルダナ帝国の姻戚であるテュランジア公国の大公が亡くなった。公国の全権を引き継ぐのはタイタニア贔屓の若き大公妃ラティーシャであったが、なぜかテュランジアはタイタニアに対して不穏な動きを見せ始める。憂慮するジュスラン・タイタニアは、タイタニアの特使としてテュランジアに赴くことを決意するが…。

タイタニアとテュランジアの交渉は決裂した。自らの愚挙によってラティーシャ大公妃を失ったテュランジア公国上層部は、周辺諸国と反タイタニア連合軍を結集し、タイタニアに挑もうとする。ヴァルダナ帝国では、藩王アジュマーンに反感を持つ貴族たちが軍務大臣エストラード・タイタニアにクーデターを促していた…。

ジュスランの授けた策によってシラクサ星域における会戦を制したアリアバート。しかし、テュランジア公国の敗滅により、帰る場所を失ったテュランジア軍の残党が海賊と化し、周辺航路は無法地帯と化してしまった。そんな中、ヒューリックを乗せた「正直じいさん」号は、補給のために惑星カガノートに着陸するが…。

反タイタニアを掲げる宇宙海賊の集団、流星旗軍がタイタニア軍の駐留する要塞「リトルビッグホーン」を陥落させた。ランカスター中将を失ったザーリッシュは、討伐軍の司令官に自ら名乗り上げる。その頃、要塞を陥落させ意気上がるドールマン率いる流星旗軍のアジトには反タイタニア分子が続々と合流していたが…。

「天の城（ウラニボルグ）」にエルビング王国の王女リディアがやってきた。王国のエネルギー鉱山の権利と引き換えに、彼女は人質になることを藩王アジュマーンに提案しにきたのだ。そして天真爛漫に行動するリディア姫により、ジュスランたちが騒動に巻き込まれていくが、アジュマーンはその様子をあえて黙認していた…。

ザーリッシュの放った追っ手をミランダの機転によってかわした「正直じいさん」号は、惑星バルガシュに到着した。その地でヒューリックはかつての部下、パジェスとワレンコフと再会するが、エーメンタールに残したリラの面影を忘れられず、せつなさを感じ始めていた。だがその頃、リラの身に最大の危険が迫っていた…。

タイタニアの追っ手から惑星バルガシュに逃れた「正直じいさん」号のヒューリックたち。その頃、タイタニア側に寝返ったかつての上司ベルティエはアルセスにヒューリックあぶり出しのための卑怯な作戦を伝える。リラを捕らえ、公開処刑すると全宇宙に流させたのだ。そんな中、リラの面影を忘れられないヒューリックは…。

リラを救出するため、罠と知りつつ惑星エーメンタールに向かうヒューリックたち。それを迎え撃つべく、ベルティエが待ち構えていた。エウリヤでの自分の計略をヒューリックの勝利により台無しにされた恨みを晴らすつもりなのだ。だが、エーメンタールの軌道上に到達したヒューリックの艦隊はなぜか動きを止めてしまい…。

リラを失うことになったヒューリックは、アルセスに仇討ちを決意した。彼に怯えて「天の城（ウラニボルグ）」に救いを求めるアルセス。だが、それに応えるように藩王アジュマーンが命じたのは実兄のザーリッシュではなくイドリスであった。イドリスはアルセスに一隻で「天の城（ウラニボルグ）」にくるよう命じるが…。

ヒューリックにより最愛の息子アルセスを失ったテリーザは、ザーリッシュに弟の仇を必ず取るよう命じる。一方、ヒューリックは、密かにリラの故郷カサビアンカの地に降り立っていた。そして「天の城（ウラニボルグ）」が手薄になった頃、その期に乗じてヴァルダナ帝国内の反タイタニア勢力も動き出しつつあった…。

反タイタニア派一掃の計略は成功したが、その代償は大きく、バルアミーの父であるエストラードまで失うこととなった。その頃、カサビアンカに密航していたヒューリックは、エウリヤで出会った靴磨きの少女カレンに再会していた。純真なカレンに接していくうち、ヒューリックはタイタニアに立ち向かうことを決意するが…。

何もいわず姿を消していたヒューリックが、「正直じいさん」号に帰ってきた。その頃「天の城（ウラニボルグ）」では、偽情報におどらされてヒューリック討伐に向かったザーリッシュが失意のまま帰還していた。だが藩王アジュマーンは、その責を問おうとせずザーリッシュにタイタニアの公敵ヒューリック討伐を命じて…。

ヒューリックの行方をつかめず焦るザーリッシュ。艦隊戦では無類の強さを誇るザーリッシュだが、たった一人の指名手配犯を追うには不向きであると、ジュスランとアリアバートもことの行方を案じていた。そのザーリッシュのもとへ、辺境の星エスタールでヒューリックの身柄を拘束したとの朗報が届けられるが…。

マフディーたちを救うため、ヒューリックはタイタニア兵の手に落ちた。だが、彼を連行したのはエスタールの警備兵であった。ヴァルダナ帝国に属さないエスタール政府は、市街地の警察権をたてにヒューリックの身柄を拘束する。そして、ヒューリックは脱出不能といわれる人工の監獄衛星クロノスに移送されてしまい…。

エストラードの後任としてイドリスが軍務大臣に任命された。イドリスは自分の影響力をさらに強めるため、近衛軍司令官の後継者として実弟のラドモーズを呼び寄せていた。藩王アジュマーンから、身内の不祥事に対する苦言を呈されるジュスランとイドリス。互いを牽制し合う二人に対して、アジュマーンが下す裁定とは…。

監獄内の暴動騒ぎの隙を突いて、クロノスから生還したヒューリックは、惑星エスタールの砂漠に潜伏する「正直じいさん」号に逃れていた。その頃、「天の城（ウラニボルグ）」にはヒューリック死亡の報がもたらされる。アジュマーンは、ザーリッシュに代わってジュスランを遺体の引き取りに向かわせようとするが…。

カナック大統領に対して、空の棺を用意しヒューリックの遺体と偽った非を理由に、ジュスランはタイタニア軍の駐留と通商の自由の放棄を迫った。そして「天の城（ウラニボルグ）」へと戻り、藩王アジュマーンにその報告をするジュスラン。そんな彼に何故ヒューリックを逃がしたかとザーリッシュとイドリスは詰め寄るが…。

エスタールから脱出した「正直じいさん」号のヒューリック一行は、辺境の惑星バルガシュに逃れていた。バルガシュの反タイタニア勢力とコンタクトを取るため、ミランダと酒場を訪れたヒューリックを歓迎する酔客たち。そこに急に踏み込んできたタイタニア兵をまいて逃げ出す手助けをしたのは女性バーテンのセラだった…。

バルガシュ政府保安部隊の制止も聞かず、ヒューリックの潜むタルハリ砂漠の洞窟を襲撃したタイタニア軍。間一髪で間に合った「正直じいさん」号がタイタニア特務艦と戦闘に入った時、ドクター・リー率いる流星旗軍の武装艦も到着し、タイタニア艦を撃破した。だが、「正直じいさん」号も敵の攻撃を受け大破してしまい…。

大破した「正直じいさん」号を見せしめのごとく攻撃するザーリッシュ艦隊。そしてザーリッシュはタルハリ砂漠の反タイタニア勢力拠点に攻撃を進めようとする。その頃バルガシュ正規軍も、無法な戦闘行為を止めるべくザーリッシュにコンタクトを取ろうとしていた。だが、それを拒絶したザーリッシュは進撃しようとして…。

撃墜された旗艦タイフーンを後にしたザーリッシュは、自ら兵を率いヒューリックが潜むタリハリ砂漠の洞窟に向かった。だが、洞窟に突入したタイタニア兵たちは、反タイタニア軍が仕掛けた策により、低酸素症で次々と倒れていた。そんな中、不死身のごとく暴れていたザーリッシュは、ついにヒューリックと対峙して…。