軍隊設立法案への投票を控えたパドメ・アミダラ議員を乗せ、ナブーのロイヤル・クルーザーがコルサント星系に到着した。しかし、クルーザーは専用着床パッドに着陸した途端に爆破され、乗員全員が死亡する。だが、乗っていたのはアミダラの影武者となっていた侍女の1人コーデだった。自分を襲う陰謀を目の当たりにしたアミダラは動揺するが、警備隊長のタイフォに連れられ、悲痛の思いで元老院へと向かうのだった。
元老院議長の官邸ではパルパティーンとジェダイ評議会の重鎮たちが会談を行っていた。パルパティーンは分離主義勢力との話し合いによる紛争解決に自信を見せるが、事態は想像以上に深刻である。そこへアミダラを筆頭とする忠誠派議員団が訪れ、アミダラは直感から暗殺未遂の首謀者がドゥークー伯爵ではないかと告げる。しかし、ドゥークーはかつてクワイ＝ガンを訓練した偉大なジェダイ・マスターでもあった。評議員たちはドゥークーの潔白を信じており、パルパティーンの進言を受け入れ、オビ＝ワン・ケノービとアナキン・スカイウォーカーを彼女の護衛につけると約束するのだった。
パドメの宿舎で、オビ＝ワンとアナキンは10年ぶりに彼女との再会を果たす。特にアナキンはこの10年間、絶えずパドメを想い続けてきたのだった。だが、彼の一途な想いに対してパドメは冷静だった。任務を逸脱する犯人の究明に自信を示し、オビ＝ワンから叱責を受けたアナキンを尻目に、彼女はジェダイの護衛に期待を寄せ、寝室へと急ぐ。アナキンは意気消沈するが、オビ＝ワンと代議員となったジャー・ジャーに励まされ、自分の役目を果たすのだった。
アミダラの暗殺を企てたのは女賞金稼ぎザム・ウェセルと、その雇い主である銀河系最強の賞金稼ぎジャンゴ・フェットである。ジャンゴは本当の依頼主を慎重に隠すため、彼女に仕事を請け負わせていたのだ。彼はザムに猛毒を持つ生物クーハンを与え、再びアミダラを襲撃させるのだった。
パドメに心を奪われたアナキンに、オビ＝ワンが個人的な恋愛感情を禁じたジェダイ・オーダーの掟を説いていたとき、寝静まったパドメの部屋にザムが送り込んだ暗殺ドロイドが到達した。ドロイドは部屋の中にクーハンを解き放つが、そのわずかなフォースの変化を感じ取った2人のジェダイが乱入する。間一髪のところでアナキンのライトセイバーがクーハンを焼き切り、オビ＝ワンはドロイドを追跡する。アナキンも宿舎を飛び出して駐車してあったスピーダーを拝借すると、師匠の後を追うのだった。追跡者を察知したザムは全速力で逃走し、コルサントの深夜の摩天楼で壮絶なスピーダー・チェイスが繰り広げられる。アナキンは無謀な運転と衝動的な行動でオビ＝ワンを困らせながらも、彼女を地上のナイトクラブに追い詰めた。2人は慎重に店の中へと入り、オビ＝ワンがライトセイバーの一撃でザムの腕を切り落とす。ジェダイは彼女に黒幕の正体を尋問するが、遠方からジャンゴの放った毒入りダーツによって、ザムは息絶えたのだった。
オビ＝ワンとアナキンがジェダイ評議会に報告を済ませると、ヨーダとメイス・ウィンドゥはオビ＝ワンに賞金稼ぎの捜索を、アナキンにはアミダラの護衛として彼女をナブーへ送り届ける任務を与える。アナキンにとってはこれは初の単独任務であり、パドメと2人きりになれる好機でもあった。彼はさっそくパルパティーンの官邸へと足を運び、投票を回避してナブーに戻るようパドメを説得してほしいと依頼する。彼はこの10年間、常に自分を気に掛けてくれたパルパティーンに深い尊敬の念を抱いていたのである。一方、オビ＝ワンは秀でた才能から傲慢になっている弟子に不安を隠せなかった。だが、メイスはアナキンこそが予言にある「選ばれし者」であるとし、オビ＝ワンに自分の弟子を信頼するよう進めるのだった。
アナキンとパドメは目立たぬよう難民を装ってナブーへと発った。そして、オビ＝ワンは謎の賞金稼ぎが残したダーツについて調査するため、旧友デクスター・ジェッスターのダイナを訪れる。知識豊富なデクスターはオビ＝ワンとの再会を喜び、ダーツの出処がクローン職人の惑星として知られるカミーノであることを教えてくれた。オビ＝ワンはその情報をもとにジェダイ公文書館でカミーノの情報を検索するが、何も見つからない。彼はヨーダに知恵を求め、この老マスターに従って修行に励む子供たちの洞察から、カミーノの情報が何者かによって削除されたことを知るのだった。オビ＝ワンはヨーダの言葉とデクスターの情報を信じ、謎の究明を求めてカミーノへと向かう。
そのころナブーへ向かう船の中では、アナキンとパドメが徐々にかつての親交を取り戻していた。2人は首都シードに到着すると新女王に謁見し、安全な湖畔に身を寄せることになる。そして2人で過ごすうちに、アナキンはパドメへの強い愛情を募らせていった。2人は熱いキスを交わし、急速に親密になっていくが、アナキンの強い情熱をよそにパドメはどうしても一線を踏み越えることができないのだった。そこには議員とジェダイという、立場と掟の問題が2人の間に立ちふさがっていたのである。アナキンは秘密の恋を持ちかけるが、現実はそこまで甘くはなかった。
地表のすべてが水に覆われ、絶えず嵐の吹き荒れる惑星カミーノに到着したオビ＝ワンは、思いがけない歓迎にたじろいだ。カミーノアンたちはジェダイの訪問を待っており、真っ先にビジネスの話を切り出してきたのである。カミーノの首相ラマ・スーは、既に発注どおり、共和国軍となる20万のクローン兵を完成させており、追加分の100万も完成間近だと説明する。また、首相は発注者としてジェダイ・マスター・サイフォ＝ディアスの名を告げるが、彼は10年前に死んだはずの人物だった。オビ＝ワンは内心驚きながらも、密かに用意されていたクローン軍を視察し、このとき彼らの遺伝子提供者が賞金稼ぎのジャンゴ・フェットであることを知らされる。オビ＝ワンはさっそくジャンゴに面会を求めるのだった。
早すぎるジェダイの訪問に驚いたジャンゴは、オビ＝ワンの質問をうまくはぐらかしつつ、雇い主はティラナスという男だと説明する。面会はすぐに終わり、ジャンゴは遺伝子提供の報酬として得た自分の完全なクローン、ボバ・フェットと共にカミーノからの逃走を準備するのだった。一方、オビ＝ワンはさっそくこの驚愕の事実をコルサントのマスターに報告し、ジャンゴを評議会で尋問するため捕らえるよう命じられる。予言には、フォースに均衡がもたらされるとき、ダークサイドが増大すると記されていた。クローン軍の存在を察知できなかったヨーダとメイスも、フォースがシスの放った暗雲に覆われているという事実を認めざるを得ないのだった。
ナブーでのある朝、アナキンは夢にうなされ目を覚ます。タトゥイーンに残してきた母シミが苦しんでいる姿を予見したのだった。彼は任務でパドメのもとを離れることができないが、パドメは自分も一緒であれば問題はないとし、2人でタトゥイーンへと出発する。やがてモス・エスパに到着した2人は、ワトーの店を訪れた。老トイダリアンはジェダイとなったアナキンを見て驚くが、既にシミは他人に売られており、ここにはいなかった。アナキンはワトーから得た情報をもとにアンカーヘッドの水分農場を訪ね、母を買い取り再婚したというクリーグ・ラーズ、その息子オーウェン、そしてオーウェンの婚約者ベルー・ホワイトサンと面会する。だが、懐かしいC-3POとの再会を果たしたものの、ここにも既に母の姿は見えなかった。クリーグ曰く、シミはタスケン・レイダーたちに連れ去られ、1ヶ月間行方不明なのだという。母の身を案じるアナキンはオーウェンのバイクを借り、砂漠の荒野を目指すのだった。
カミーノではジャンゴとボバが愛機＜スレーヴI＞で逃走しようとしているところだった。オビ＝ワンは2人を制止しようとするが、ジャンゴはジェダイに戦いを挑み、激しい肉弾戦となる。結局ジャンゴは逃走するが、オビ＝ワンは彼の船に追尾装置を取り付けていた。彼は＜スレーヴI＞を追って辺境の惑星ジオノーシスへと到達する。軌道上の小惑星帯でも激しい宇宙戦が行われ、オビ＝ワンはジャンゴを見失うが、賞金稼ぎが地上に降りたのは明らかだった。彼はそのまま追跡を続け、ジオノーシスに通商連合の貨物船団が停泊している事実を発見する。続いて地表の尖塔の中を探索し、大規模な製造工場で無数のバトル・ドロイドが作られていることも明らかになった。そしてオビ＝ワンはさらに驚くべき事実を目の当たりにする。ヌート・ガンレイ総督をはじめとする分離主義勢力に加担する有力企業の幹部たちと共に、ドゥークー伯爵がこの惑星を訪れていたのである。彼らはこの会合で正式に独立星系連合を旗揚げし、大量生産したドロイド軍をもって共和国とジェダイに対抗することを確認していた。大規模な戦争の準備が着実に進んでいたのである。
タスケンのキャンプにたどり着いたアナキンは、小屋の中についにシミの姿を発見する。親子は10年ぶりの再会を喜ぶが、衰弱しきっていたシミは愛する息子に抱かれたまま、安らかに息を引き取るのだった。母を失ったアナキンの怒りは凄まじく、彼は怒りにすべてを任せてタスケンを皆殺しにする。このときのフォースの騒乱ははるか彼方のコルサントにまで届き、ヨーダとメイスに恐ろしい警告を告げるのだった。母を抱いてラーズ家の農場に戻ったアナキンは、こうなったのは自分が未熟なせいであり、オビ＝ワンが十分な修行をさせないからだと訴える。パドメはアナキンをなだめ、その後、シミの葬儀がしめやかに行われた。アナキンは母の死に決意を新たにするが、そこにオビ＝ワンからの連絡が入る。ジオノーシスからの報告をコルサントに中継してほしいというものだった。
オビ＝ワンは評議会のマスターや元老院議員たちに恐るべき事実を伝えるが、その直後にドロイドに発見され、捕らえられてしまう。この非常事態を前に忠誠派の議員たちも、クローン軍を使って分離派を攻撃すべきだというアスク・アック議員や、それでも先制攻撃は許されないというベイル・オーガナ議員の意見によって紛糾していた。だがこれ以上議論をしている猶予はなく、マス・アメダ副議長はパルパティーン議長に非常時特権を与えるべきだと提案する。議会で絶大な信頼を持つアミダラ議員ならばこのような動議を提出できるが、彼女はコルサントにいない。ここで代役を買って出たのは、彼女の代理に任命されていたジャー・ジャーだった。彼は議会で一世一代の演説を行い、パルパティーンへの支持を訴える。すると議長の共和国への愛と不退転の決意が満場一致の賛意をもってそれに応えるのだった。パルパティーンは直ちにクローン軍を正式採用し、分離主義勢力の打倒を宣言する。それを受けたジェダイ・オーダーも、メイスがオビ＝ワン救出のため他のジェダイと共にジオノーシスへと向かい、ヨーダがクローン軍を受け取るべく、カミーノへと向かうのだった。一方、タトゥイーンに留まるよう厳命されたアナキンも、パドメとR2、3POを連れ、オビ＝ワンを助けるためジオノーシスへと発ってしまう。
捕らわれの身となったオビ＝ワンの前にドゥークーが現れた。彼は腐敗した共和国が既にシス卿ダース・シディアスによって牛耳られていること、10年前のナブー事件もシスの後ろ盾があったこと、そして自分が共和国を裏切ったのもシスを倒すためであることを告げる。ドゥークーはオビ＝ワンを仲間にと誘うが、彼はそれを敢然と拒否するのだった。やがて、彼を救出するために到着したのはアナキンたちだった。彼らはドロイド製造工場へと侵入するが、大乱闘の末、捕らえられてしまう。アナキンとパドメはオビ＝ワンと共に共和国からのスパイ容疑によって処刑されることになるのだった。このときパドメはアナキンへの愛を告白する。3人は大勢のジオノーシアンが観戦する処刑闘技場へと運ばれ、3体の猛獣たちに身を委ねられた。VIPボックスではドゥークー、ジオノーシスのポグル大公、ガンレイ総督とその副官、フェット親子がその光景を楽しんでいる。だが、そこに突如としてマスター・ウィンドゥが割り込んできたのだった。
メイスの登場と同時に200人のジェダイが闘技場になだれ込む。アナキンたちも解放され、ジオノーシアンたちが逃げ惑うなか、代わりに何千体ものバトル・ドロイドが押し寄せてきた。メイスも観戦ボックスを追われ、闘技場での戦いに参戦する。この戦いは熾烈を極め、メイスは強敵のジャンゴを倒すが、これまでの歴史上類を見ないほどの数のジェダイが殺害されてしまう。そしてついに残りのジェダイたちも追い詰められ、ドゥークーに降伏を迫られるのだった。だが、メイスがそれを拒否したとき、上空からクローン軍を引き連れたヨーダが降りてくる。圧倒的なクローン軍の戦力によって形成は一気に逆転し、闘技場は破壊されたドロイドの残骸に埋め尽くされた。やがて戦場は砂漠の荒野へと移動し、ジェダイ率いるクローン軍とドロイド軍との全面戦争へ突入する。ドゥークーたちも司令室へと引き上げるが、残されたボバはひっそりと父の亡骸にすがるのだった。
分離派の指導者たちは正体不明のクローン軍の出現に予期せぬ戸惑いを見せていた。ドロイドの全軍を投入しても、とても数が足りないのだ。形成は著しく不利に傾き、ガンレイは早々とジオノーシスから撤退してしまう。そしてさらに戦いが続き、ドロイド軍の敗北が決定的になると、ポグル大公も軍を撤収させるのだった。彼はこのとき、密かに開発を進めていた最終兵器の設計図を、共和国の手に落ちる前にドゥークーに託す。それは想像を絶する大きさと破壊力を誇る宇宙要塞兵器だった。伯爵はこの設計図をコルサントにいる謎のマスターへ届けるべく、自船の待機するドックへと急ぐのだった。
アナキンとオビ＝ワン、パドメを乗せたガンシップがドゥークーのバイクを視界に捉えた。彼らは伯爵の後を追うが、ジオノーシアンの戦闘機による砲撃を受け、パドメが砂漠に転落してしまう。オビ＝ワンは彼女を助けようとするアナキンを一喝し、任務の優先を説いた。やがて彼らはドゥークーの格納庫へと到達し、伯爵と対峙することになる。だが、元ジェダイ・マスターのドゥークーは余りにも強かった。さらに彼はフォースのダークサイドを受け入れており、アナキンをフォースの電撃で失神させると、オビ＝ワンをもあっさりと倒してしまう。再起したアナキンも再び戦いを挑むが、右腕を切断され、再び倒されてしまう。そこへ姿を現したのはマスター・ヨーダだった。ライトサイドとダークサイド、両者の達人が持てる力を尽くして激しくぶつかり合う。決闘はフォースの戦いからライトセイバー戦へと移り、敵わぬと悟ったドゥークーはフォースで巨大な支柱を倒すと、動けなくなった師弟を襲うのだった。そしてヨーダが2人を助けようと気を逸らした隙に、宇宙船で逃走してしまう。パドメが駆けつけたときにはすでに戦いは終った後だった。
数日後、コルサントの見捨てられた工業地帯にドゥークーの船が到着した。彼を待ち構えていたのはダース・シディアスである。ドゥークー伯爵、いやシス卿ダース・ティラナスは、彼の新しいマスターに戦争が始まったことを告げるのだった。一方、ジェダイはジオノーシスの戦いで多くの仲間たちを失っていた。ヨーダはドゥークーがダークサイドに落ちたことに強い懸念を抱く。そのころ、議員たちが見守る前で、無数のクローン兵が分離派の惑星へ向けて出撃を開始していた。悲痛な面持ちのベイル・オーガナとは対照的に、パルパティーンは決意に満ちた表情でその光景を眺めている。銀河系と共和国に破壊と殺戮をもたらす凄惨な戦い、クローン大戦がついに幕を開けたのだった。
そのころ、ナブーの湖畔ではアナキンとパドメが3POとR2に見守られて秘密の挙式を行っていた。ジェダイの掟は結婚を禁じている。だが、2人にはもはやそんなことは関係なかったのだ。