インペリアル級スター・デストロイヤー＜ストーカー＞から多数のプローブ・ドロイドが放たれた。その中の1機はホスにも到達し、さっそく反乱軍の秘密基地の捜索を開始する。そのころ、ホスの雪原では反乱軍の英雄ルーク・スカイウォーカーとハン・ソロがトーントーンに跨って定期パトロールを行っていた。ハンは何の進展もなく基地に帰還するが、ルークは隕石を調査するため移動しようとしたところを雪獣ワンパに襲われる。一方、それを知らないハンは基地に戻ると、ライカン将軍に同盟軍から離れたいと告げるのだった。ヤヴィンの戦いから既に3年が経過しており、彼の首には痺れを切らしたジャバ・ザ・ハットから多額の懸賞金が掛けられていたのである。事実、ハンはこれまでにも自分を狙う賞金稼ぎと遭遇しており、このまま生き延びるにはもはや一刻の猶予も残されていないと悟っていたのだった。
タトゥイーンへ戻るべく愛機＜ミレニアム・ファルコン＞の整備へと向かうハンを、レイア・オーガナが呼び止める。彼女はハンの力が必要だと言い、彼を引き止めようとするが、ハンが望んでいたのは反乱軍のリーダーとしてではなく、レイア個人としての慰留だった。ハンは彼女に明らかな好意を寄せていたが、2人の感情はすれ違い、説得は物別れに終わってしまう。ハンがルークの消息不明を知ったのは＜ファルコン＞の修理を行っていたときだった。夜を迎えるとホスの気温は急激に低下し、ルークが生きて帰って来る確率も非常に低くなる。ハンは友人を助けるため、再びトーントーンで極寒の雪原へと向かうのだった。
凍てつくような吹雪のなか、ハンはわずかな生命反応を手がかりにルークの捜索を進めていた。だが、外の気温は急激に低下し、ハンの命も危険に晒されるようになる。エコー基地でもハンからの連絡が途絶え、ついに防寒扉が閉じられると、レイアとチューバッカの表情に絶望の色が横切るのだった。そのころ、ルークはワンパの洞窟に逆さづりの状態で捕らえられていた。意識を取り戻した彼は未熟ながらもフォースの流れを掴み、氷に突き刺さったライトセイバーを引き寄せる。異変に気づいた雪獣が彼を襲うが、ルークはワンパの腕を一刀両断し、命からがら洞窟を逃れるのだった。だが、厳寒の雪原で彼は再び倒れてしまう。意識がもうろうとするなか、ルークを呼びかけたのはフォースと一体となって姿を現した亡き師、オビ＝ワン・ケノービだった。老師は惑星ダゴバへ行き、マスター・ヨーダの教えを乞えと告げる。そこにハンが現れ、親友を死の淵から救い出したのだった。だが、ハンのトーントーンも息絶え、2人はシェルターを設置して極寒の夜をすごすことになる。そして翌朝、2人はエコー基地を出撃したスノースピーダーの捜索隊によって発見され、無事に基地へと戻ることができたのだった。
バクタ・タンクで治療を終えたルークを中心に、再び英雄たちが顔をそろえる。エコー基地には宇宙船の発進禁止令が出ており、足止めされたハンは不快感を示すが、それを自分と別れたくないレイアの好意と曲解し、彼女を困惑させる。レイアは当てつけにルークとキスを交わし、ハンを嫉妬させるのだった。すると、偵察機が不審な物体を発見したとの報告が入る。謎の物体は帝国軍の暗号を発信しており、基地内に不安と緊張が走った。そして、ハンとチューバッカが調査に向かい、それが帝国軍のプローブ・ドロイドであることが判明すると、ライカン将軍は直ちに全軍の撤退を命じるのだった。
ホスからの送信がダース・ヴェイダー率いる死の小艦隊に届いた。旗艦スーパー級スター・デストロイヤー＜エグゼキューター＞の艦橋でピエット艦長からの報告を受けた暗黒卿は、フォースの直感でホスに反乱軍の秘密基地があることを確信する。捜し求めるスカイウォーカーもそこにいるのだ。艦隊司令官のオゼル提督は異論を挟むが、ヴェイダーの信念は揺るがなかった。彼は全艦をホス星系へ向けさせ、総攻撃の準備を命じたのだった。
やがて帝国艦隊がホスの軌道上に姿を現した。しかし、同盟軍は攻撃に備えて強力な防御シールドを作動させており、帝国軍は軌道からの砲撃を封じられてしまう。ヴェイダーはその失態への怒りをオゼルに向け、彼を処刑すると共にピエットを提督へと昇格させた。そして、ヴェイダーはヴィアーズ将軍にAT-AT部隊による地上攻撃を命じたのである。一方、反乱軍はイオン・キャノンで地上から援護射撃を行いながら、貨物船を脱出させていた。ハンは＜ファルコン＞の修理に追われながらもルークに二度目の別れを告げ、ルーク率いるローグ中隊が帝国軍のAT-ATと対峙する。しかし、無敵のAT-ATの前に反乱軍は大打撃を受け、徐々に前線を後退させていった。そして、ついにヴィアーズ将軍によってエネルギー基地が破壊されると、ヴェイダー自ら地上に降り立ち、ルークの捜索を開始するのだった。
エコー基地に総員退去命令が鳴り響く。だが、ハンとチューバッカは未だに＜ファルコン＞の修理を行っており、レイアも最後の貨物船の脱出を見送っているところだった。レイアの身を案じるハンは、彼女を＜ファルコン＞に乗せてホスを脱出する。だが、軌道上で待ち受けるスター・デストロイヤーが、執拗に彼らを追跡するのだった。ハンはハイパードライブを使って一気に逃走しようとするが、故障によってジャンプができない。極めて一方的な追跡劇が展開され、やがて＜ファルコン＞はホス近郊の小惑星帯へと逃げ込んだ。だが、帝国軍は恐ろしいほどの執念でハンの船を追い、ようやく追っ手を振り切ると、＜ファルコン＞は巨大な岩に開いた洞窟の中へと身を隠すのだった。
一方、無事にホスを脱出したルークは、オビ＝ワンの助言に従い、R2-D2を伴ってXウィングで惑星ダゴバへと向かう。沼の惑星ダゴバは文明社会とは程遠い無人の惑星であり、とても偉大なジェダイ・マスターが住んでいるような場所ではなかった。彼はさっそくヨーダを探すが、逆にルークを見つけたのは小柄なエイリアンの老人だった。老人は馴れ馴れしい態度で彼を困らせるが、ヨーダのところへ案内すると言い、ルークを自分の家へ招く。そこで老人はルークに様々な質問を投げかけ、あたかも以前から彼を知っているかのように話しかけるのだった。やがてルークは我慢の限界に達し、怒りをあらわにする。仲裁に入ったのはオビ＝ワンの声だった。この老人こそが旧共和国のジェダイ・マスター・ヨーダだったのだ。ルークは彼に入門の許可を求め、オビ＝ワンも同意を告げる。ヨーダはルークが今ある現実を見ず、未来ばかりを見つめていることに渋りながらも、銀河に光をもたらす希望を求めて、この若きジェダイを弟子とするのだった。
＜ミレニアム・ファルコン＞の徹底捜索を命じるヴェイダーに、突如としてパルパティーン皇帝からの呼び出しがかかる。ヴェイダーが皇帝のホロの前に跪くと、パルパティーンはデス・スターを破壊したスカイウォーカーの息子がフォースに騒乱を巻き起こしていると告げ、警告する。ヴェイダーはダーク・マスターに、ルークをダークサイドに引き込むか、それを拒むなら抹殺すると請け負うのだった。彼は即座に銀河中から腕利きの賞金稼ぎたちを招集し、＜ファルコン＞に賞金を掛ける。その中には悪名高きボバ・フェットの姿も見えるのだった。
洞窟の中で、ハンたちは＜ファルコン＞の修理に取り掛かっていた。その途中、ハンは再びレイアに言い寄り、徐々に心の間を狭めていく。しかし、この場所は決して安全とはいえなかった。船の外にはパワー・ケーブルを齧るマイノックが飛び交っており、一行は害獣退治に外に出るが、そこで驚愕の事実に気づくことになる。そこは洞窟ではなく、想像を絶するほどの大きさをしたスペース・スラッグの体内だったのだ。ハンは急いで＜ファルコン＞を発進させて難を逃れるが、スター・デストロイヤー＜アヴェンジャー＞に発見されてしまう。ハイパードライブはまだ直っておらず、逃走は不可能だった。ここで彼は機転を利かせ、＜アヴェンジャー＞に特攻すると見せかけて艦橋の裏側に＜ファルコン＞を貼り付けた。彼らはレーダーからも姿を消し、うまく帝国艦隊を出し抜くことに成功すると、船を修理するためベスピンへと向かう。そこには旧友ランド・カルリジアンの統治する採鉱都市、クラウド・シティがあるのだ。しかし、ヴェイダーに雇われた賞金稼ぎの中でただ1人、＜スレーヴＩ＞に乗るボバ・フェットだけが獲物を視界に捉えていたのである。
ダゴバで修行に励むルークは、ヨーダから最初の試練としてダークサイドの強い、薄暗い洞窟の中へ入るよう命じられる。彼は丸腰で行けと言われるが、武器を身に付け、洞窟の奥へと進むのだった。すると、そこにヴェイダーの幻影が現れる。驚いたルークはライトセイバーを起動し、ヴェイダーに切りかかるが、彼が切り落した仮面の下には、自分自身の顔が隠されていたのである。その後も、ルークは幾度となく失敗を繰り返し、そのたびに叱責を受けていた。沼に沈んだXウィングを前に見た目で不可能を判断し、フォースを感じることを諦めてしまうこともあった。だが、ヨーダは大きさは関係ないといい、Xウィングを引き上げることでフォースの偉大さを見せ付ける。また、ヨーダは若き弟子に未来を予見するよう指示し、ルークは瞑想の中で、雲に浮かぶ都市と、そこで苦しむハンやレイアの姿を垣間見るのだった。彼は仲間を助けに行かなければならない衝動に駆られ、ヨーダとオビ＝ワンの制止を振り切って出発の準備を進める。2人の師は、ルークがダークサイドの誘惑に駆られることを危惧しており、まだヴェイダーと戦うには早すぎると戒めた。だが、ルークは行ってしまう。オビ＝ワンは困惑するヨーダに、彼が最後の希望だと告げるが、ヨーダはもう一人の存在をほのめかすのだった。
クラウド・シティではハンたちがランドの歓迎を受けていた。生粋のギャンブラーであるランドは＜ファルコン＞の前の所有者でもあり、ハンとは過去に確執もあったが、現在はこの都市の執政官としてティバナ・ガスの採鉱事業を手がける実業家として収まっている。しかし、レイアは一見平和に見えるこの都市に何か不穏な気配を感じていた。C-3POが行方不明になり、数時間後にバラバラになって発見されたのである。ハンもランドを完全に信用しているわけではなく、修理を終えたらすぐに発つつもりだと説明する。しかし、レイアの直感は正しかった。フェットに導かれた帝国軍が先に到着しており、ランドもやむなくハンを裏切っていたのである。ヴェイダーはルークを捕らえるための囮として彼らを利用しようと考えていたのだ。ハンとレイアは互いに愛し合っていたことを確認するが、彼は実験台としてカーボナイト冷凍にかけられ、フェットに引き渡されてしまう。そして、レイアとチューバッカも帝国軍の捕虜として連行されることになるのだった。その後、ルークが到着すると、ヴェイダーは彼を誘い出し、ダークサイドへの誘惑をはじめたのである。
隙を突いて帝国を裏切ったランドは、レイアとチューイーを解放してソロの救出へと急ぐ。だが、あと一歩及ばず、＜スレーヴI＞は彫像と化したハンを載せ、ジャバ・ザ・ハットの待つタトゥイーンへと発ってしまう。彼らはやむを得ずこの都市から脱出するため、＜ファルコン＞へと急ぐのだった。
一方、ヴェイダーとルークは互いのライトセイバーを手に、激しくぶつかり合っていた。ときにルークは父を殺した暗黒卿を圧倒し、ヴェイダーはかつての師であるオビ＝ワンに教えを受けた若きスカイウォーカーの力量に感心するが、両者の実力の差は歴然としていた。やがてルークは強大なフォースのダークサイドに押され、右手を失い、傷だらけとなって追い詰められる。そして、勝利を決定的なものにしたヴェイダーは、ルークに驚愕の事実を告げるのだった。自分こそがお前の父親なのだと。ルークはその言葉を激しく否定するが、フォースはそれが事実だと告げていた。ヴェイダーは驚くべき可能性を秘めた息子をダークサイドへと誘い、皇帝亡き後の銀河を統治しようと持ちかける。だが、ルークは誘惑を断ち切り、自ら奈落の底へと落ちていくのだった。クラウド・シティの底辺で絶体絶命の危機に立たされたルークは、フォースを通じてオビ＝ワンに、そしてレイアに助けを求める。彼の心の声に気づいたのはレイアだった。既に追っ手から逃げ切っていた彼女はランドに戻るよう要求し、直感を頼りにルークを見つけると、彼を救出したのである。辛くも一命を取り留めたルークだが、彼の心はオビ＝ワンとヴェイダーが語った相反する2つの事実の間で複雑に揺れていた。
ベスピンを脱出した＜ファルコン＞に、ヴェイダーの＜エグゼキューター＞が迫る。ハイパードライブは帝国軍によって切られており、ヴェイダーは再びルークを捕らえるため、トラクター・ビームで＜ファルコン＞を引き寄せるつもりだった。だが、R2がハイパードライブの回線を接続したことで、ようやく＜ファルコン＞は自由を得たのだった。
その後、反乱軍の集合地点で治療を受けたルークは、レイアと2体のドロイドと共に、＜ミレニアム・ファルコン＞の出発を見送っていた。ランドとチューバッカがハンを救出するため、タトゥイーンへと発ったのである。ルークも後から合流すると告げ、仲間とのしばしの別れを前に、決意を新たにするのだった。