辺境の砂漠の惑星タトゥイーンの軌道上で、反体制派の帝国元老院議員の1人、レイア・オーガナ姫の乗艦するオルデランの外交船＜タンティヴィIV＞が、帝国軍のインペリアル級スター・デストロイヤー＜デヴァステーター＞の追撃を受けていた。レイアの船は執拗な攻撃によって主反応炉を破壊され、航行不能にさせられてしまう。帝国軍は＜タンティヴィIV＞を拿捕すると、ストームトルーパー部隊を船内に突入させ、乗員たちとの間で激しい銃撃戦が展開された。＜デヴァステーター＞を指揮するのは、皇帝の側近の1人であり、帝国軍の重鎮でもあるダース・ヴェイダー卿だった。彼はレイアが反乱同盟軍のスパイであると睨み、この船が受信したとみられるデス・スターの設計図を探していたのだ。
しかし、危機を察知したレイアは忠実なアストロメク・ドロイドのR2-D2に設計図を託しており、彼をプロトコル・ドロイドのC-3POと共に脱出ポッドで船外に射出させていた。スター・デストロイヤーも脱出ポッドの射出を確認していたが、ドロイドしか乗っていないポッドに生命反応はなく、見過ごされていたのである。船内に設計図の形跡が既にないことが分かると、ヴェイダーはレイアをスパイ容疑で捕らえ、タトゥイーンに回収部隊の派遣を命じるのだった。その後、＜タンティヴィIV＞は跡形もなく破壊され、レイアへの支持が多数を占める元老院には、遭難事故として報告されることになる。
2体のドロイドは荒涼としたタトゥイーンの砂丘海に漂着する。そして、レイアからの密命を受けたR2と何も知らない3POは口論となり、互いに別々の方向へと歩むのだった。だが、やがて2体は砂漠で廃品回収業を営むジャワたちに発見され、彼らの巨大なサンドクローラーの中で再会を果たす。その後、ドロイドたちはジャワの廃品バザーで売りに出されるのだった。
3POとR2を購入したのは、アンカーヘッドの近郊で水分農業を営むオーウェン・ラーズと、その甥ルーク・スカイウォーカーだった。ルークはオーウェンからさっそくドロイドたちの整備を命じられ、偶然にもR2が内部に記録していたレイアのホロ・メッセージの一部を発見する。彼女はオビ＝ワン・ケノービという人物に助けを求めており、R2も自分の本当の主人はオビ＝ワンだと言うのだ。ルークはオビ＝ワンという人物に心当たりはないが、砂漠の端に住む変わり者の隠者、ベン・ケノービとは面識があった。メッセージの続きを見ようとする彼は、R2の指示通りに行動規制ボルトを外すが、ドロイドは続きを再生しようとしない。彼は苛立ちながらも食事に向かい、叔父にオビ＝ワンとベンとの関係を問いただすのだった。だが、オーウェンはベンを不快に思っており、オビ＝ワンはルークの父親と同じころに死んだと語るだけだった。また、ルークはドロイドの労働力が増したことで、かねてからの夢だった帝国アカデミーへの進学許可を求めるが、それも無下に断られてしまう。友人たちは次々とこのつまらない惑星から出て行ってしまい、取り残された彼にとって、今の人生は切ない試練でしかなかったのである。
ルークがドロイドたちのもとへ戻ると、R2が姿を消していた。彼は規制ボルトがなくなったため脱走し、オビ＝ワンへの任務を果たしに向かったのである。凶暴なサンド・ピープルが徘徊する夜は危険であるため、ルークは翌朝の捜索を決めるのだった。そして翌朝、ルークが3POを連れて砂漠を捜索していたころ、帝国軍の分遣隊も脱出ポッドにドロイドが乗っていたことを突き止め、捜索を開始していた。やがてルークはジャンドランドの荒地でR2を発見するが、サンド・ピープルの襲撃を受け、気を失ってしまう。彼を助けたのは老ベン・ケノービだった。彼は自分こそがオビ＝ワン本人であると語り、ルークたちを家へと連れて行く。そこで、ベンは自分とルークの父親が共に旧共和国のジェダイ・ナイトであったこと、そして自分の弟子だったダース・ヴェイダーが帝国に寝返り、ルークの父を殺害したのだということを告げ、この青年に父の形見のライトセイバーを手渡すのだった。そして、R2がベンにレイアからのメッセージを再生する。その内容は、R2に記憶されているデス・スターの設計図を養父ベイル・オーガナの待つオルデランへ届けてほしいというものだった。ベンは高齢を理由にルークの同行を求めるが、彼には断るしかなかった。オーウェンがそれを許すはずがないのだ。
一方、デス・スター内部では帝国軍上層部が会合を開いていた。この要塞兵器の最高司令官グランド・モフ・ターキンは、パルパティーン皇帝が帝国元老院の永久解散を宣言したことを報告する。反乱軍の力を侮るまいとするタッグ将軍と、デス・スターの威力に絶対的な自信を示すモッティ提督とで意見が割れるなか、ターキンはヴェイダーが設計図を取り戻し、反乱軍基地の所在を必ずや見つけてくれるだろうと確信していた。そのときこそ、デス・スターは一撃で反乱軍を壊滅させ、帝国の体制を磐石のものとすることができるのだ。ヴェイダーは反乱軍の秘密基地の場所を突き止めるべく、捕虜となったレイアへの尋問を開始するのだった。
ベンをアンカーヘッドの街へ送る途中、ルークは焼け爛れたサンドクローラーと無数のジャワの焼死体を発見する。タスケン・レイダーの仕業に見せかけられてはいたが、これが帝国軍のストームトルーパーによるものなのは明らかだった。惨殺されたジャワたちはルークに2体のドロイドを売った者たちであり、彼は自分の家にも危険が迫っていることを直感する。ルークはベンの制止を振り切り、全速力で我が家へと戻るが、そこで待っていたのは無残な姿に変わり果てた叔父夫妻だった。故郷に留まる目的を失ったルークは、ベンと共にオルデランへ行き、父の後を継ぐべくフォースの道を学ぶことを誓うのだった。
彼らはタトゥイーンの有数の宇宙港都市モス・アイズリーに到着する。帝国軍の検問をベンのフォースで無事に切り抜けた彼らは、オルデランへのチャーターを引き受けてくれる腕利きのパイロットを雇うため、荒くれ者の集う酒場へと入っていった。そこで彼らは＜ミレニアム・ファルコン＞の船長である密輸業者のハン・ソロと、その相棒、ウーキーのチューバッカを雇うことになる。だが、ハンは犯罪王ジャバ・ザ・ハットの仕事に失敗し、多額の借金を背負っている身だった。このときも賞金稼ぎが取立ての使いとして現れ、酒場に一騒動を巻き起こしたほどである。彼は法外な値段でこの仕事を請け負うと、愛機の整備にドックへと戻るが、そこにはジャバ自らが待ち受けていた。ハンはこの仕事の終わりに利息を付けて必ず返済すると約束し、その場をやり過ごす。やがてルークとベンが訪れるが、タトゥイーンを発とうとした瞬間、密告を受けて彼らを追ってきたストームトルーパー隊に襲撃される。一行は間一髪で難を逃れるものの、既に＜ファルコン＞は帝国軍にマークされていたのである。
タトゥイーンの軌道上には2隻のスター・デストロイヤーが待ち構えていたが、＜ファルコン＞はハイパースペースへジャンプし、オルデランを目指していく。船内でルークはベンからフォースの修行を受け、徐々にジェダイとしての悟りを開いていった。そのころ、デス・スター内では薬物による尋問にも屈しなかったレイアを精神的に追い詰めようと、ターキンはこの要塞兵器をオルデラン星系へと移動させていた。彼はレイアに対し、反乱軍基地の場所を教えなければ、故郷を破壊すると脅したのである。さすがのレイアもこの脅迫には口を割るほかなく、ダントゥイーンの名を告げるのだった。だが、ターキンは無情にもスーパーレーザーを発射し、レイアの目の前でオルデランを爆破させてしまう。帝国にとって、反乱同盟軍の絶大な支援者であるベイル・オーガナはどうしても抹殺しなければならない人物であり、この攻撃は帝国の威信とデス・スターの恐怖を広めるための効果的な見せしめとなったのである。
オルデランと共に消え去った何億もの人々の叫びが、フォースの騒乱となってベンを襲った。しかし、彼はルークへの教えを続け、若き弟子の成長を確かめる。やがて＜ファルコン＞はオルデラン星系に到着するが、既にそこに惑星の姿はなく、ただ瓦礫の海が広がっているだけだった。ベンは帝国軍が惑星を破壊したのだと直感するが、ハンは付近をパトロールしていたTIEファイターを追跡し、事情を確かめようとする。やがて彼らの目の前に現れたのは月ほどの大きさを持つ宇宙ステーションだった。強力なトラクター・ビームに捕らえられた＜ファルコン＞は、なす術なくデス・スター内部へと引き寄せられ、拿捕されてしまう。帝国軍はこの船が要塞の設計図を持ってモス・アイズリーから逃走した貨物船であることを確認し、内部の徹底調査を開始するのだった。ルークらはストームトルーパーに変装して船内から脱出し、作戦を練ることになる。
ダントゥイーンを調査した偵察隊からの報告により、ターキンはレイアの言葉が嘘だったことを知る。彼は怒り狂い、直ちに彼女の処刑を命じたのだった。一方、ベンは若者たちに多くの惑星の運命を委ね、一人でトラクター・ビームを遮断しに行く決意をする。また、ルークとハン、チューバッカは監房区画にレイアが捕らえられていることを突き止めると、ドロイドたちを残して彼女を救助に向かうのだった。彼らはチューバッカを捕虜に見立てて監房区画へと進み、乱闘の末、レイアを発見する。だが、侵入者の存在が発覚したことでデス・スター内全域に非常警報が出されており、彼らは袋小路に追い詰められてしまうのだった。仕方なくレイアはダスト・シュートへと潜り込み、4人はゴミ処理場に立てこもる。そこには怪物ダイアノーガが棲んでおり、さらにゴミ圧縮装置が作動して、彼らは絶体絶命の危機に立たされるのだった。
そのころ、ベンは首尾よくトラクター・ビームの切断に成功していた。一方、ダース・ヴェイダーもフォースを通じてかつての師の存在を感じ取っており、20年前の決着をつけるべく、1人で彼の足取りを追っていた。また、ルークたちも際どいところでC-3POとR2-D2に救われ、ゴミ処理場からの脱出に成功する。こうして自由の戦士たちはおのおので＜ファルコン＞を目指すことになるが、ベンを待ち受けていたのはシスの暗黒卿ダース・ヴェイダーだった。かつての師弟が再びライトセイバーを交え、＜ファルコン＞の目の前で死闘を繰り広げる。しかし、老オビ＝ワンの力は衰えていた。彼は若き弟子に未来を託し、ヴェイダーの光刃を受けてフォースと一体となる。思いがけないベンの死にルークは錯乱するが、ベンの声が走れと告げていた。＜ファルコン＞で飛び立った彼らはTIEファイターの追撃をかわし、ハイパースペースへと逃れたのである。
＜ミレニアム・ファルコン＞はレイアに導かれ、反乱軍の秘密基地のあるヤヴィン4へと向かう。だが、船体には帝国軍の追尾装置が取り付けられており、デス・スターも急速にヤヴィン星系を目指していた。彼らはこのためにわざと取り逃がされたのである。反乱軍の将軍たちはR2から得た設計図を分析し、デス・スターの唯一の弱点を突き止めていた。反応炉から伸びる直径わずか2メートルの排熱ダクトにプロトン魚雷を直撃させることができれば、この要塞兵器を破壊することができるのだ。ルークは反乱軍パイロットの一員として銀河の命運を賭けた戦いに参加する決意を固めるが、ハンとチューバッカはそれを自殺行為だと言い捨て、ジャバ・ザ・ハットへの借金の返済に戻ってしまう。やがてデス・スターがヤヴィン星系に姿を現し、反乱軍の戦士たちが戦闘機で飛び立っていく。基地で旧友ビッグズ・ダークライターと思いがけない再会を果たしたルークは、彼と共にレッド中隊の一翼となってこの決戦に挑むのだった。
デス・スター表面からの砲撃と、TIEファイターによる迎撃によって、反乱軍の戦闘機は徐々に数を減らしていく。また、銀河一のパイロットとされるヴェイダーも専用TIEファイターで出撃し、驚異的な腕で歴戦の勇者たちを葬っていった。最初にターゲット・ゾーンに突入したYウィングのゴールド中隊も1機を残して全滅し、続いて突入したレッド・リーダー率いるXウィング小隊も全滅させられてしまう。残るはルーク、ビッグズ、そしてウェッジ・アンティリーズの3機のXウィングのみとなるが、その直後にウェッジは戦線を離脱し、ビッグズもヴェイダーによって撃墜されてしまった。ヴェイダーはルークのXウィングを追い、そのパイロットが強いフォースの持ち主であることに気づく。そしてとどめを刺すべく狙いを定めたその瞬間、ハンの歓声と共に＜ファルコン＞が助けに現れたのだった。ヴェイダーの機は味方のTIEと接触してデス・スターの外側に大きく弾き飛ばされる。すると、ルークに再びベンが語りかけてきた。彼は師の言葉に従ってフォースに身を委ね、見事にプロトン魚雷を排熱ダクトへと直撃させたのである。ヤヴィン4を射程に捉えたデス・スターは、砲撃する直前に宇宙の塵と化したのだ。
ヤヴィン4では、反乱軍の戦士たちが劇的な大勝利に歓喜していた。ルーク、ハン、チューバッカは英雄として表彰され、正式に反乱軍の勇者として迎え入れられたのである。