宇宙世紀0083年。オーストラリアの地球連邦軍トリントン基地に向かう一隻の強襲揚陸艦があった。その揚陸艦アルビオンに積まれていた２機の試作ガンダム。トリントン基地に所属するテストパイロットのひとり、コウ・ウラキはその威容に目を奪われる。一方、アナハイム・エレクトロニクスのシステム・エンジニア、ニナ・パープルトンは、ガンダム試作２号機が核装備であることを見抜いたコウの観察力に舌を巻いていた。しかし、核弾頭を装填した直後、２号機はジオンを名乗る男に強奪されてしまう。それと時を同じくして、突然の攻撃がトリントン基地を襲った。眼前で奪われた２号機を止めるため、コウは試作１号機に乗り込む。基地から逃亡しようとする２号機の前に立ちはだかるコウの１号機。２機のガンダムの対峙が、新たなる戦いの幕開けとなった。

１号機のコクピットの中で、コウは初めての実戦に萎縮していた。一方、２号機を奪った男は余裕の表情でコウを退ける。２号機の逃亡を許したコウたちは、休む間もなく追撃に移った。一旦はジオンの回収艇を捕捉するコウたちだったが、２号機は追撃を逃れてさらに逃亡を図る。コウはそこで初めて２号機を奪った男の名を知る。男の名はアナベル・ガトー。“ソロモンの悪夢”と恐れられたジオンのエースパイロットだった。圧倒的な力を持つ敵に戸惑うコウを、指揮官サウス・バニングの力強い言葉が励ます。深い霧が覆う中、死闘を演じるコウの１号機とガトーの２号機。しかし、ガトーはコウたちの必死の攻撃を尻目に、霧の中へと消えていった。敵を逃した悔しさに、無念の涙を流すコウ。コウたちを追いかけて一部始終を目にしていたニナは、彼の後ろ姿に不思議な感情を抱くのだった。

ジオン残党の襲撃によって、トリントン基地は壊滅的な打撃を受けた。荒れ果てた基地に佇むコウは、無力感に打ちひしがれていた。しかしニナは、初めての戦闘で１号機の性能を引き出したコウに、ただならぬ才能を感じる。そんな中、アルビオンは２号機の追撃任務に就くことが決定し、新たなパイロットが補充されてくる。そのパイロットのひとり、ベルナルド・モンシアは、ガトーと戦って生き残ったというコウの実力を信じることができなかった。一方、コウは２号機奪還の任務が自分の手を離れることを知り、アルビオンに志願しようとする。そんなコウに絡むモンシア。ふたりは１号機パイロットの座を賭けて、MSで戦うことになる。ベテランパイロットの技量に圧倒されるコウだったが、なんとかモンシアに勝利した。アルビオンの艦長エイパー・シナプスはコウの才能に目を留め、１号機のパイロットとして迎え入れるのだった。コウは慣れ親しんだ基地を後にし、２号機奪還の任務に就いた。

２号機を追うアルビオンは、アフリカの大地を進んでいた。しかし、出撃して一週間、ガトーの影すら掴めず、クルーのストレスは頂点に達していた。問題の絶えないアルビオン艦内に、シナプスですら苛立ちを隠すことができずにいた。一方、ジオン残党が潜むキンバライト鉱山基地では、ガトーと２号機を迎え入れる歓声に湧き上がっていた。２号機をHLVで宇宙に打ち上げるため、着々と準備を進めるガトーたち。その頃アルビオンでは、アナハイムのスタッフ、ニック・オービルがジオンのスパイであることが判明していた。シナプスたちはわざとオービルを逃がし、ジオンの潜伏場所を突き止めようとする。キンバライトのジオン残党はHLV打ち上げの時間を稼ぐため、アルビオンに肉迫する。コウたちの必死の攻撃も空しく、ガトーと２号機は宇宙へと上っていった。

２号機追撃任務の舞台は宇宙に移っていた。アルビオンは味方艦と合流し、ガトーが逃げ込んだ暗礁宙域を捜索しようとする。その艦内では、地上用の１号機にこだわるコウと、そんなコウに苛立つニナの間に些細なすれ違いが起こっていた。コウが１号機のパイロットであることを、感情的に否定してしまうニナ。厳しいニナの言葉に、コウは頑なになるのだった。一方、茨の園に帰還したガトーを待っていたのは、跋扈するシーマ・ガラハウだった。茨の園に接近するアルビオンに対し、攻撃をかけるシーマ艦隊。その戦闘のさなか、デラーズ・フリートの決起を宣言するエギーユ・デラーズの演説が響く。ニナの制止を聞かずに１号機で出撃したコウだったが、シーマが駆るゲルググMの前に１号機は大破する。傷付いていく１号機を目の当たりにして、ニナはようやくコウを好きな自分の気持ちに気付いた。

アルビオンは補給と１号機の宇宙用への換装のため、月のフォン・ブラウンに寄港していた。ニナは傷付いたコウの心を癒すため、必死で１号機の換装に取り組む。一方、久々の上陸許可に沸き返るアルビオンのクルーたち。しかしコウはひとり、１号機を大破させたショックに沈んでいた。あてどもなくフォン・ブラウンの街を彷徨うコウは、最下層でジャンク屋を営むケリィ・レズナーのもとに辿り着く。揺れる自分の気持ちを整理するため、ケリィとともに彼のモビルアーマーを修理しようとするコウ。しかし、シーマと接触するケリィの姿を目撃し、彼がジオンのパイロットであったことを知る。行き場所を失いかけたコウの傍らに、彼を気遣うニナが佇む。その時コウは、自分の心の奥底にくすぶっているものがあることに気付く。その気持ちに答えを出すため、コウはケリィのもとに戻った。夜通しでMAの修理を続けるふたり。そして、ケリィに別れを告げたコウは、改修が完了した１号機フルバーニアンのコクピットに座るのだった。

アルビオンに戻り、フルバーニアンのトライアルを続けるコウ。その姿を目にして、ニナの心は充足感に満たされる。コウと１号機をサポートするために再びアルビオンに乗ろうとするニナだったが、アナハイム社はそれを許そうとはしなかった。さらに、コウとのすれ違いが、彼女をアルビオンから遠ざけようとしていた。一方、デラーズ・フリートに参加しようとしていたケリィは、パイロットとしての自分が必要とされていないことを知る。己の再起を賭けてガンダムとの勝負に臨むケリィ。ケリィの行動に困惑しながらも出撃するコウ。ふたりは月面を舞台に激しい戦いを繰り広げる。その時、ニナがふたりの前に姿を現す。戦いを止めようとするニナだったが、戦闘に巻き込まれてしまう。その光景を目の当たりにして、コウは怒りのままにケリィを撃破する。ケリィは後悔することなく閃光の中に消えた。そして、コウは命を取り留めたニナに、そばにいて欲しいと告げる。その言葉に応え、ニナはコウの胸の中に飛び込むのだった。

フォン・ブラウンを離れたアルビオンは、コンペイトウで行われる観艦式に備えて哨戒任務に就いていた。そんな中、コウは初めて訓練戦でバニングに勝利する。バニングは教え子の成長を喜びながらも、自分の衰えを痛感していた。一方、作戦の準備を進めるガトーは、不穏な動きを見せるシーマに警戒感を強める。その頃、シーマ艦隊は連邦艦との密会ポイントに向かっていた。その目的は、観艦式の観閲旗艦バーミンガムとの接触。バニングの活躍によって、アルビオンのMS隊はシーマ艦隊を撃退した。その戦闘のさなか、バニングはデラーズ・フリートの作戦要綱を手に入れる。彼らが『星の屑』と呼ぶ作戦の全貌を知り、驚愕するバニング。しかし次の瞬間、戦闘で傷付いていた彼の機体は爆発し、バニングは帰らぬ人となった。精神的な支柱を失ったアルビオンを、重苦しい空気が包む。彼らの悲しみをよそに、様々な者たちの思惑を孕んだ観艦式の日が近づいていた。

観艦式の日、遠くアステロイドベルトから地球圏に到達する艦隊があった。デラーズ・フリートと合流するため、アクシズから訪れた先遣艦隊であった。その頃、コウたちはソロモン海域に集結しつつあるジオン残党との戦いを繰り広げていた。いつ果てるともしれない戦いに、疲労の色を隠せないコウ。一方、ガトーは連邦軍の追及をかわして出撃する。新たな敵影に、疲れを癒す間もなく迎撃に向かうコウたち。デラーズ・フリートの散発的な攻撃を退け、連邦軍は観艦式を決行する。しかし、ガトーの２号機はその攻撃を陽動として単機でコンペイトウに接近していた。ガトーの動きを知り、コンペイトウへと急行するコウのフルバーニアン。コウの焦りをよそに、ガトーは核バズーカの照準をバーミンガムにロックする。ガトーの叫びとともに放たれた核バズーカは、コンペイトウの連邦艦隊を光の中へと消し去るのだった。

ガトーが放った核によって、連邦艦隊は壊滅的な打撃を受けた。コンペイトウから退避するガトーの２号機を、屈辱に身を焦がすコウのフルバーニアンが追撃する。熾烈な一騎討ちを演じるふたり。その対決は、相討ちという形で幕を閉じた。閃光となってソロモン海に消える２機のガンダム。その光景を前に、ニナは泣き崩れる。無事アルビオンに戻ったコウだったが、コンペイトウへの核攻撃が『星の屑』の終焉だとは思えずにいた。一方ニナは、コウがこれ以上の戦いに身を投じることを恐れた。コウはその理由を知らない。それと同時刻、輸送中のコロニーをシーマ艦隊が襲撃する。コロニーのミラーを破壊してコースを変え、月へのコロニー落としを実行するシーマ。コロニー激突の放電で光が満ちる宙域に、シーマの嘲笑が響き渡る。その嘲笑を背に、アルビオンはガンダム試作３号機を受け取るためにラビアンローズへの針路を取った。

コロニー落としを目前にしてもなお、連邦首脳は事態を冷ややかに傍観していた。一方、ラビアンローズに到着したアルビオンを待っていたのは、デラーズ・フリート追撃任務の解除通告だった。その頃、コロニーに迫るコンペイトウの追撃艦隊の先鋒は、ガトーのノイエ・ジールによって撃破されていた。焦るコウたちを尻目に、コロニーは月へと近づく。ガンダム試作３号機の開発に携わったルセット・オデビーは、連邦軍による３号機の開発凍結に不満を抱き、コウに３号機を託そうとする。さらにデラーズ・フリートは、アナハイムとの密約を利用してコロニーの推進剤に点火し、月への落着直前でそのコースを地球へと変えた。激変する状況にコウは、ニナの反対を押し切って３号機に乗る決意を固める。しかし、コウたちの行動を阻止しようとするナカッハ・ナカト少佐の凶弾に、ルセットは倒れた。３号機をニナに任せて息を引き取るルセット。ニナは、３年前のガトーとの関係と向き合う決断を迫られる。ニナの決意は３号機に命を吹き込み、コウは３号機を駆って最後の戦いに挑もうとしていた。

コロニーの地球落下を阻止できる最終防衛ライン、阻止限界点。そのタイムリミットまで、あと10時間を切っていた。コウの３号機はコロニーへの突破口を開くため、ガトーのノイエ・ジールと死闘を繰り広げる。その頃、デラーズ・フリートの旗艦グワデンの艦橋は、シーマによって占拠されていた。デラーズを裏切り、連邦軍に寝返ろうとするシーマ。一方、コウたちの奮戦も空しく、コロニーは阻止限界点を越える。次の瞬間、デラーズ・フリートの戦闘停止を告げる通信が戦場に流れる。連邦軍はシーマの離反を利用して、ソーラ・システムⅡでコロニーを破壊しようとしていた。デラーズは眼前にある地球とコロニーに目をやり、星の屑の完遂をガトーの手に託す。命を賭けたデラーズの決意に、ガトーもまた決意を固める。理解できない男たちの行動に、シーマはデラーズに向けた銃の引き金を引く。陰謀渦巻く宇宙に、ガトーの絶叫が響き渡った。

ソーラ・システムⅡを防衛する連邦艦隊とシーマ艦隊を、ガトーの意地の猛攻が襲う。一方コウは、バニングやケリィの死を無にするシーマたちの行動を目の当たりにして、無念の怒りに身を震わせた。コウやガトーが激しく戦う中、コロニーに向かって照射されるソーラ・システムⅡ。しかし、コロニーは止まることなく地球へと落下していく。ガトーはコロニーの最終軌道修正を行うため、コロニー内部に向かう。ニナもまた、単身コロニーに向かっていた。目論見を外され激昂するシーマを撃墜し、コロニー内部に進入するコウ。そこでコウはガトーを撃ち、ニナはガトーを庇った。コウの制止を振り切り、ガトーとともに消えるニナ。コウはひとり残され立ち尽くす。しかし、ガトーはニナを拒み、決着をつけるためにコウを待った。ふたりの戦いはソーラ・システムⅡによって阻まれ、ガトーはコウの前から姿を消す。連邦追撃艦隊に最後の突撃をかけるガトー。彼の命が消えゆくのを、ニナは見届けることしかできなかった――。戦いの後、コウはオークリー基地に立っていた。そこには、愛する者との再会を心から喜ぶニナの姿があった。