Story
完全なネタバレなので、クリアしてから見てください。
プロローグ
クロードとエイトボール
2001年のリバティーシティ。
リバティーシティ銀行に強盗が現れる。強盗達は裏口から飛び出すと、迎えの車に一目散に走っていく。
そのうちの一人が本作の主人公であるクロード（Claude）である。しんがりのクロードは、追手に向けて威嚇射撃を行うと、仲間のほうへ足を進める。
ここで事件が起きる。角を曲がったクロードは、仲間の女に銃を向けられ、躊躇なく銃撃されてしまう。彼は裏切られたのだ。一命をとりとめたクロードだったが、その後有罪判決を受けて刑務所に護送されることになる。
クロードら囚人を乗せた護送車がキャラハンブリッジを渡っているところで、正体不明のテロリストが現れる。彼らの目的は護送中の幹部の奪還のようだ。彼らは手際よく幹部を救出すると、何処ともなく姿を消す。この騒ぎをチャンスと見た他の囚人たちも動き出す。警官らを素手で殴り倒すと手錠の鍵を奪い、護送車の外に出る。その瞬間、テロリストが仕掛けた爆弾が爆発し、キャラハンブリッジが破壊される。これにより、キャラハンブリッジは当面通行できなくなる。
クロードともに自由をつかんだもう一人の囚人はエイトボール（8-Ball）という。エイトボールの提案で、彼の隠れ家に共に向かうことになる。手をけがしていたため、運転はクロードが行った。キャラハンブリッジを下っていく最中で、パトカーとすれ違うが難なくやり過ごす。
車はレッドライト地区の一角に到着する。ここがエイトボールの隠れ家のようだ。彼らは囚人服を着替えると、再び車に乗り込む。エイトボールの話では、ルイージ・ゴトレッリ（Luigi Goterelli）という人物にツテがあるという。
彼らは車で数分の場所にあるルイージのナイトクラブに向かった（Give Me Liberty）。
クロードという名前は本作中では明らかになりません。
ルイージ・ゴトレッリ
ルイージ・ゴトレッリ
ナイトクラブの裏口からルイージが姿を現す。彼の女（＝従業員）をここに連れてくればまた仕事をやるという。近所にある病院に車を向かわせると、そこにはミスティ（Misty）という女がいた。彼女をナイトクラブに送り届けると、最初の仕事が完了となった。（Luigi's Girls）
その後、彼の従業員をヤク漬けにした売人をしばいたり（Don't Spank Ma Bitch Up）、ミスティをとある人物の元へ送迎する仕事を任せられたりする（Drive Misty For Me）。
ミスティを送り届けた先には、ジョーイ・レオーネ（Joey Leone）がいた。彼は、ルイージが所属する組織のドンの息子であるらしい。クロードの評判はルイージからすでに伝わっており、この初顔合わせは好意的に迎えられた。
さらに、敵対ギャングディアブロのポン引きを始末したり（Pump-Action Pimp）、警察のパーティに大勢の女を送り込む仕事（The Fuzz Ball）をこなしたりして、ルイージからの信頼を獲得する。
ジョーイ・レオーネ
ジョーイ・レオーネ
ジョーイのガレージに向かうと、待っていたとばかりに仕事を依頼される。
借金を踏み倒したフォレッリ兄弟を爆死させたり（Mike Lips Last Lunch）、トライアドのシマで薬物の売人を始末（Farewell 'Chunky' Lee Chong）したり、チャイナタウンの現金輸送車を強奪（Van Heist）するなど、仕事はだんだんと危険なものとなっていく。
ある日、ジョーイのガレージには見知らぬ男がいた。トニー・シプリアーニ（Antonio "Toni" Cipriani）である。この時点では正体がわからないが、彼は組織の幹部でありクロードのことを聞き及んでいるようだ。彼をセント・マークスにある彼の母親の店に送り届ける（Cipriani's Chauffeur）。
その後は、フォレッリの部下の死体入りの車をスクラップにし（Dead Skunk In The Trunk）、銀行強盗の運転手役（The Getaway）をこなすと、ジョーイからの仕事は一段落する。
トニー・シプリアーニ
トニー・シプリアーニ
セント・マークスのレストランに行くと、トニーが待っていた。彼の話では、先日返り討ちにあった洗濯屋にリベンジをするという。
洗濯屋のバンを破壊（Taking Out The Laundry）した脅しが効き、用意されショバ代を回収しに行く。これはトライアドが仕組んだアンブッシュであったが、何とか金の回収に成功する（The Pick-Up）。
ここで、ドンからの招集がかかる。トライアドとの戦争も匂わされる。ジョーイが用意したリムジンに共に乗り込むと、道中でルイージとトニーを拾う。途中トライアドの襲撃があったものの、セント・マークスの丘の上にあるドンの邸宅にたどり着く。邸宅には、レオーネファミリーのドンであるサルバトーレ・レオーネ（Salvatore Leone）が待ち構えていた。彼は、部下や息子の労をねぎらうと、いよいよクロードと対面する。部下たちからの評価はすでに十分に伝わっているようで、クロードは非常に好意的に迎え入れられた（Salvatore's Called A Meeting）。
ついにトライアドとの戦争が始まる。部下とともにチャイナタウンに向かうと、トライアドからの猛反撃を受ける。戦場さながらの状況の中、トライアドの幹部3人を始末する（Triads And Tribulations）。さらに、とどめとしてトライアドの魚工場を爆破する（Blow Fish）。
サルバトーレ・レオーネ
サルバトーレ・レオーネ
邸宅では、ドン直々の指示を受ける。ドンの愛人であるマリア（Maria Latore）をシャブパーティに送り届ける（Chaperone）。コロンビアン・カルテルと内通していると疑われる“ネズミ”を見つけ出し、始末する。この内通の現場には、カルテルの幹部であり、クロードの仇でもある「あの女」の姿もあった（Cutting The Grass）。
コロンビアン・カルテルの資金源である麻薬を製造していると思しき巨大船舶を破壊するミッションを指示される。これに成功すればファミリーに迎え入れられるという（まだファミリーじゃなかったの!?）。これまで何度かお世話になっている、爆弾のスペシャリストであるエイトボールを訪ねる。爆弾の費用として自費で10万ドル用意すると作戦決行となる。スナイパーライフルを片手に、埠頭の倉庫の屋根に上るクロード。エイトボールは船のタラップのそばに身をひそめる。船の上は多数のカルテルの手下が見張りを行っている。クロードが放った一発の銃声を皮切りに時が動き出す。入口付近の見張りが倒れたことを確認すると、エイトボールが船上に向かって走り出す。次々と射殺されていく見張りたち。船の最奥に爆弾をセットすると、きびすを返すエイトボール。その直後、船は大爆発を起こし、海の藻屑と消える（Bomb Da Base）。
ラスト・リクエスト
大仕事をやり終えたクロードは、大手を振って邸宅に向かう。いよいよファミリーへの仲間入りかと思いきや、サルバトーレから別の仕事を押し付けられる。今のクロードにとっては簡単な内容であったが、現場に向かっていると、マリアからのメッセージが入る。
「その車は罠。」
サルバトーレから処分を指示された車には罠が仕掛けられているという。危険を察知したクロードは、車には乗らずマリアとの待ち合わせ場所に向かう。そこにいたマリアは、自身のついた嘘により、誤解したサルバトーレがクロードをカルテルに売ったと告白する。マリアとクロードは命を狙われているという。マリアの旧友であるアスカ・カセン（Asuka Kasen）とともに小型の船舶に乗り、ストートン島に逃げ延びる。アスカはクロードのためにストートン島の隠れ家を用意してくれる（Last Requests）。
このタイミングでキャラハンブリッジの修復が完了し、2島の間を自由に行き来できるようになる。
アスカ・カセン
アスカ・カセン
アスカの協力を得るためには、マフィアとの関係を完全に断ち切る必要がある。アスカからサルバトーレの行動予定を聞いたクロードは、ルイージのクラブの向かいにあるビルの屋上からサルバトーレを射殺する。サヨナラ・サルバトーレ（Sayonara Salvatore）。
アスカの元に戻ると、兄のケンジ・カセン（Kenji Kasen）を紹介される。ケンジからも任せたい仕事があるようだ。サルバトーレの死によってレオーネファミリーの動きがさらに活発になった。今後の仕事を行いやすくするため、アスカの指示でマフィアの監視を一掃する（Under Surveillance）。
アスカを監視しているパパラッチを排除（Paparazzi Purge）し、汚職警官に賄賂を渡す（Payday For Ray）。この汚職警官はレイ・マショウスキー（Ray Machowski）という。賄賂を届けた際に気に入られたクロードは、今後レイとの関係も持つことになる。
おとり警官を始末したところでアスカからの依頼が落ち着く（Two-Faced Tanner）。
ケンジ・カセン
ケンジ・カセン
島の南東部にあるカジノの屋上に行くとケンジが待っていた。彼はクロードに一礼をすると、仕事が欲しければ実力を見せるようにと指示する。
幹部を警察署から脱獄（Kanbu Bust-Out）させることに成功すると、次は3台の高級車を盗む仕事（Grand Theft Auto）を依頼する。
続いて、ジャマイカ系ギャングのヤーディーズとカルテルの会合を襲撃（Deal Steal）、ストートン島の各店舗からショバ代を徴収（Shima）、路上にいる薬物の売人を始末（Smack Down）等の仕事が依頼される。
なお、ケンジのミッションをこなさなくてもストーリーには影響ない。
レイ・マショウスキー
レイ・マショウスキー
レイと公園の地下トイレで密会すると、相当に腹を立てているのか、かなり高圧的な態度で話しかけてくる。
証人保護を受けている人物を始末（Silence The Sneak）すると、かつての戦友の護衛を命令される。護衛対象は元軍人であるフィル・キャシディ（Phil Cassidy）である。彼は兵器マニアであり、その兵器を狙ってカルテルが襲撃を計画しているという。フィルが待ち構える施設を訪れると、悪態をつかれながらも大量の兵器を手渡される。ほどなくしてカルテルの襲撃を受けるが、2人の力を合わせて撃退する。この働きによりフィルに気に入られ、今後強力な武器を融通してもらえるようになる（Arms Shortage）。
レイからの依頼はまだ続き、街の大物に関する証拠物件を破棄し（Evidence Dash）、海で釣りをしているレイの相棒を抹殺する（Gone Fishing）。
すると、激怒したレイがクロードに突っかかる。先日始末したはずの証人がまだ生きているというのだ。その証人を護送中の救急車に体当たりをすると、全身を硬い（本当に硬い）ギプスで覆われた証人が地面に転落する。クロードは証人を丹念に何度も轢くことで今度こそ証人の口を塞いだ（Plaster Blaster）。
ドナルド・ラヴ
ドナルド・ラヴ
ストートン島南部にある超高層ビルに行くと、トレーニング中の男性が声をかけてくる。彼はドナルド・ラヴ（Donald Love）といい、ラジオ局を運営しているラブ・メディアの社長である。先日のレイからの依頼で破棄した証拠物件はドナルドのものであり、彼はその働きに感謝する。
ドナルドからの依頼で、誘拐された彼の友人をカルテルの施設から救出する（Liberator）。続いて、ヤクザとカルテルを故意に対立させるため、ヤクザの幹部であるケンジをカルテルに扮して暗殺する（Waka-Gashira Wipeout）。
セスナから海に投下される密輸品をボートで回収（A Drop In The Ocean）すると、第三の島であるショアサイド・ベイルに行けるようになる。
カタリーナとの対峙
ドナルドのところに戻ると、先ほど回収した密輸品はおとりであり、本物はセスナの中にあるという。ブツを回収するべく空港の敷地に向かうがブツは消失している。周囲を調査すると、持ち去ったのはカルテルだということに気づき、一路、ストートン島の建設現場に向かう。建設現場にいるカルテルの手下を蹴散らし、リフトを使って上層階へ向かう。
そこにいたのは、仇であるカタリーナ（Catalina）とその部下のミゲール（Miguel）であった。二人はブツを回収して建設現場から立ち去ろうとしているところだった。咄嗟に威嚇射撃を行うクロード。ブツを持っているミゲールは落ち着けと言い、カバンを床に置く。その直後、カタリーナはミゲールを背後から銃撃し、ビルから飛び降りて行方をくらます。
そこに、アスカが姿を現す。彼女は兄のケンジを殺害したのはカルテルであると思い込んでおり、カルテルに強い恨みを抱いている。床に倒れこんでいるミゲールを角材で容赦なく何度もしばき、情報をはかせようとする。
クロードは、ミゲールを哀れみともとれる複雑な表情で見下ろしながら、現場を立ち去る（Grand Theft Aero）。
レイの遁逃
公園のトイレを訪れると、追い詰められたレイの様子があった。もはや彼の手に負えない状況になっているという。彼を飛行機で高跳びさせることになる。橋はCIAによってマークされているため、地下トンネルを使って空港に向かう。途中若干の攻撃を受けるものの、レイを空港に送り届けることに成功する。礼として防弾性能を持った自動車をクロードに与え、空港ターミナルに駆け込む（Marked Man）。
後にマイアミが逃亡先であることをにおわせる。
ドナルドのプラン
先日建設現場で奪還したブツをショアサイド・ベイルのとある場所に運搬する計画だという。道中、カルテルの激しい襲撃があるが、クロードの的確な動きにより輸送車は目的の場所に到着する（Escort Service）。今度は、先ほどの輸送車の運転手を逃がすため、クロードがおとりとして街を逃げ回ることになる（Decoy）。
高層ビルに戻るとドナルドの姿はなく、そこには空になった箱が残されているだけであった。彼方の空には旅客機が見える。ドナルドの行方は誰も知らない（Love's Disappearance）。
拷問の末に
建設現場では、アスカによる拷問が続いていた。情報は出そろっていないものの、カタリーナがクロードを抹殺すべく暗殺団を編成したことがわかる。クロードは暗殺団を待ち伏せ場所までおびき寄せ、ヤクザと協力して退治する（Bait）。
建設現場ではまだ拷問が続いている。続く情報では、カタリーナの計画でヤーディーズが薬物の販売を始めたという。販売スポットとなっている露店コーヒーショップを壊滅させる（Espresso-2-Go!）。
建設現場に戻ると今度はマリアがミゲールをつついていた。拷問はマリアのほうがうまいという。カタリーナのブツを搭載した飛行機が間もなく着陸するという情報を得ていた。一路飛行場に向かうと、ロケットランチャーによって飛行機を撃墜する。ばらまかれたブツを回収すると、建設現場に戻る（S.A.M.）。
そこにはアスカとミゲールの亡骸があった。カタリーナによるものだろう。そばには手紙が残されていた。
「マリアの命が惜しければ50万ドルを用意しろ」
クロードは最後の戦いに向けて決意を固める（Ransom）。
カタリーナとの決着
カタリーナ
身代金の50万ドルを用意してシダーグローブの邸宅に赴く。ここはカタリーナの本拠地である。
敷地の入口ではカルテルの手下が待ち構えていた。金の入ったカバンと武器を没収されると、敷地内へと促される。
そこにはカタリーナとマリアがいた。マリアは腕を締め上げられている。カタリーナはただのビジネスだったと、クロードを遠慮なくののしる。カバンの中身を確認したカタリーナは、部下にクロードの射殺を命じるとその場を立ち去る。
クロードは一瞬のスキを突いて部下を倒す。すかさずピストルを奪うと、敷地内のカルテルを皆殺しにする。邸宅の敷地を出たところで、ヘリで逃走するカタリーナの姿を見る。ダムのほうへ向かったようだ。
車を飛ばしてダムへ向かう。ダムの敷地内はカルテルによって極めて強固な警備がなされていたが、クロードは怯むことなく前進する。
ダム施設の最奥部にいるマリアを解放すると、ロケットランチャーを手に取る。クロードが発射したロケットはヘリに命中し、ヘリは木っ端みじんになる。戦いは終わった（The Exchange）。
クロードとマリアはダムの施設を歩いてゆく。マリアは、あなたのことを気に入ったなどと早口でまくしたてるが、クロードは相手にせず歩き続ける。しかし、マリアの口は止まらない。その口を塞ぐかのように一発の銃声が響く……。
Grand Theft Auto III - 完 -
最後、マリアがどうなったのかについては意見が分かれています。