Story
完全なネタバレなので、クリアしてから見てください。
ヴィニーとマイク
ヴィニーとマイク
2000年のリバティーシティ。
チャイナタウンの片隅で、言葉を交わす二人の男がいた。一人は本作の主人公マイク（Mike）、もう一人はマイクの兄貴分であるヴィニー（Vinnie）である。マイクらは、リバティーシティを脱出して真っ当な人生を送るため、悪銭を稼ぐ日々を送っていた。そんな中、ヴィニーはマフィア絡みの仕事を引っ張ってくる。マイクは乗り気ではなかったが、ヴィニーはこれが成功すれば大金を得て夢がかなうと意気込む（Jump Start）。
マフィアのヤクを自ら使い込んでいる売人を始末（Dirty Laundry）すると、マフィアはマイクたちの脱出に協力してくれることになる。脱出に向けた準備として高性能のスポーツカーを盗む（Hot Wheels）。続いて、マフィアの代理として保護料を徴収して回ったり（Ill-Gotten）、低下しつつあったマフィアの権威を示すため数人のギャングを始末したりした（Payback）。
偽の身分証明書を入手するため、ヴィニーの旧友であるエイトボール（8-Ball）を訪ねる。彼は、爆弾のスペシャリストであるが、偽の身分証明書も用意してくれた（Fake IDs）。
脱出の準備は整った。ヴィニーはマイクをチャイナタウンに呼び出すが、そこにヴィニーの姿はなかった。ページャーに計画変更の連絡が入ると、今度はキャラハン・ブリッジのそばに向かう。ヴィニーが乗っていると思われる車に近づいた瞬間、車が大爆発し、ヴィニーが死亡してしまう。マイクは、相棒と引退後のために貯めた財産をすべて失ってしまった。見計らったかのように警察が現れる。マイクは、エイトボールの好意を受け入れ、しばらく彼のところに身を寄せることになる。エイトボールは、爆弾を調べて黒幕を特定する意向をあらわにする（Getaway）。
エイトボール
エイトボール
ヴィニーの遺体はエイトボールのところに移送していたが、遺体が傷み始めたため処理することになる。近所のジャンクヤードにあるクラッシャーを使用し、遺体を乗せた車ごと処理を行った。マイクは心痛の中、犯人の特定に向けて決意を新たにする（Twisted Metal）。
エイトボールの依頼で、ハイローラー相手の女を自宅に送りがてら探りを入れたり（Ill Repute）、危険な物品を輸送したり（Droppin' Bombs）、エイトボールの友人に手を出したスコレッリという男に仕返しをする（Scorelli）。
ここで、エイトボールが事件の手掛かりをつかむ。ヴィニーはジョニー（Jonnie）という名のバーテンダーと繋がりがあったという。本日面会が予定されているというので、マイクはその場所に向かう。ジョニーはヴィニーの死を知らなかったが、ヴィニーへの借金の埋め合わせとして犯人探しに協力すると約束する（Love Boat）。
ジョニー
ジョニー
しばらくジョニーの下で彼の手伝いをすることになる。ジョニーへの借金を踏み倒している者を始末して回ったり（Time's Up）、ジョニーのバーの女性客を家に送ったり（Sober Driver）、特殊な「酒」を集めて回ったり（Happy Hour）、新装開店のライバル店を爆破したり（Grand Opening）、密輸商人からロケットランチャーを奪取したり（Pocket Rocket）、禁煙法案を通そうとしている上院議員を「説得」したりする（Political Will）。
ある日、細工したトランプで大儲けをしたフレディという男から、いくらかの金を取り戻す。ジョニーのバーに戻るとそこは血の海となっており、ジョニーは息絶えていた。その瞬間、バーから大急ぎで立ち去る車の音が聞こえる。マイクは外に飛び出し車の後を追う。車は、ストートン島のニューポート・ドックに消えた（Show the Money）。
キング・コートニー
キング・コートニー
銃を構えて小屋に踏み込むマイク。そこにはキング・コートニーという男がいた。しかし、キングは慌てるどころか、マイクをたしなめる。キングの話では、彼はジョニーに金を貸しており、彼の部下が取り立てに行ったところ、既にジョニーは死んでいたという。キングはキングで被害者であり、犯人を見つけることを望んでいる。キングに協力することで犯人に近づけると考えたマイクは、レースに出場したり（Race to Run）、コロンビアン・カルテルのコーヒー配達ルートを襲ったりする（Latin Coffee）。
ここで、キングから新たな情報がもたらされる。今回の事件にはカルテルのボスであるシスコ（Cisco）が関係しているという。まずは、シスコの勢力に打撃を与えるため、彼の部下を殺害する（The Big Score）。このミッションにはキングの部下も参加するはずだったが、道が渋滞していたため不参加となった。いよいよ、公園のレストランで食事を終えて一服しようとしていたシスコと対峙する。
シスコは強気な態度を示していたが、マイクが鉄拳制裁を食らわせると落ち着きを取り戻す。マイクが事件について追及するが、そのようなチンケな犯罪には関与していないという。しかし、心当たりはあるといい、ヤーディーとヤクザという2つのギャングの名前をほのめかす。詳しい話は、自身の要望に応えてからだと勿体ぶる（Fine Dining）。
シスコ
シスコ
マイクはシスコの要求に応じて、シスコが開発した麻薬密輸用の靴を売りさばいたり（Flying High）、航空監視装置の製造工場を爆破したりする（Factory Wages）。
ある日、下校中のユカという少女を誘拐する。ユカは、ヤクザのボスであるアスカの姪である。ユカをシスコのところにあずけると、アスカへの脅迫を行うと言い残し、シスコから一方的に関係を切られてしまう。マイクは、少女（ユカ）にだけは危害を加えるなと言い残す（School's Out）。
アスカ・カセン
アスカ・カセン
何処からかマイクの手腕を聞きつけたアスカ・カセン（Asuka Kasen）から、ページャーに呼び出しが来る。
アスカは、自身の姪が誘拐されたため、彼女を救出できる人物としてマイクにたどり着いたという。マイクは複雑な思いを抱きつつ、身代金の2万ドルを抱えて引き渡し場所に行く。身代金は持っていかれてしまったが、ユカの居場所を知っているマイクにとっては問題なかった。見張りを始末して鍵を奪うと、ユカが幽閉されているバスを出発させる。ユカはマイクに気づくと、「マイク様、お元気ですか」と述べる。マイクの口添えにより、幽閉中は相応の厚遇を受けていたと思われる。ユカをアスカの元に送り届けると、アスカからベッドルームに誘われるがやんわり断った（Kid's A Hero）。
マイクをダーリンにしたがっているアスカとの関係はしばらく続く。保護料を支払っていないカジノを爆破したり（Ante Up）、ライバルのアメフトチームのクオーターバックの腕を折ったり（Two-Hand Toss）、彼女の誘いを断った映画スターからワニ革の靴を奪ったりする（Scorned Lover）。
アスカから少しだけ情報がもたらされ、ジョニーとヴィニーを殺害した犯人は同一人物だということが分かる。
続いて、傷んだフグを卸した運転手を連行したり（Sue Me Sushi）、マフィアのごろつきを家宝の日本刀でしばいて年季奉公に送ったりする（Down The River）。
犯人についての情報をつかんだというアスカだが、その前にしてほしいことがあるといわれ、彼女の業務を妨害しているポン引きを始末する。アスカの元に戻ると、彼女の愛慕の情は極限まで強まっており、マイクはベッドルームを受け入れる。
翌日、脚の感覚がなくなっていたマイクは、アスカから聞き出した爆弾魔の居場所に踏み込むが、一歩遅く、爆弾魔は死んでいた。しかし、現場に残されたページャーから、爆弾魔はヴィニーの事件に関係していることと、次の仕事の依頼者がショアサイド・ベイルのWichita Gardenにいることを突き止める。マイクは、マフィアや警察の追跡を振り切りながら、ショアサイド・ベイルに向かった（Bad Pimpin'）。
真相の行方
ショアサイド・ベイルに上陸すると、シスコからページャーに連絡がある。これは罠であると。マイクは、ひとまずシスコに話を聞きに行く。シスコは、空港の飛行機内に「本部」を構え、いつでも逃亡できそうな様相であった。シスコの話では、殺害された爆弾魔は彼の仕事相手でもあり、黒幕を突き止めたいようだ。何かあればシスコ達も加勢することを約束する。Wichita Gardensに到着したマイクは、予想通り待ち伏せに会う。爆弾魔を殺害した黒幕が仕込んだようだ。マイクは待ち伏せを蹴散らすと、シスコのところに戻る。
シスコは、ユカの誘拐の件でアスカから狙われており、いつでも逃亡できるようにここにいるという。一方で、爆弾魔殺害の犯人を突き止める強い意志も示す（Mystery Killer）。
別の日には、重要な会議に出席するシスコの代わりに囮となり、ヤーディーやマフィアを釣りながら街中を走り回る役を担う（Decoy Disaster）。
空港に戻ったマイクが目にしたのはシスコの死体だった。現場を走り去った車を追跡し、運転席から引きずりおろした男の顔を見て驚くマイク。その男はヴィニーだった。ヴィニーは財産を独り占めするため、自身の死を偽装していたのだ。この期に及んで泣き言を並べるヴィニーだったが、心労辛苦の日々を送る羽目になったマイクには全く届かなかった。マイクはヴィニーをくず野郎とののしると、容赦なく彼の命と財産（$10万）を奪う（Truth Revealed）。
フィナーレ
エイトボールからSOSの連絡が入る。彼は彼でヴィニーから命を狙われていたようだ。お互いの無事に安堵する二人であったが、マイクがヴィニーを殺害して金を奪ったという噂が広まっており、カルテルなどの「殺したい奴リスト」のトップにいるという。そんな中、シスコをマイクが殺害したと思い込んでいるカルテル連中が襲撃してくる。エイトボールは負傷してしまったが、何とか襲撃を払いのける。しかし、警察の手によってエイトボールは逮捕されてしまう（Love of Money）。
カルテルのトップを抑えれば襲撃を回避できると考えたマイクは、シスコの後釜としてトップの座に就いた男を路上で襲撃する。男とはひと悶着あったが、マイクの力に押されて降参する。男は、自身を殺しても問題は解決しないこと、マイクの命を狙っているのはキング・コートニーであることを述べ、カルテルとの和解を求める（Taking Revenge）。
街中に散らばっている、ヤーディーの部下を殺害して回っていると、共通の敵がいるとしてアスカからの連絡がある（Smackdown）。
久しぶりにアスカと対面する。アスカの話では、キング・コートニーの勢力がヤクザの支配地を侵害しつつあり、キングを始末するために、マイクに協力する用意があるという。
ショアサイド・ベイルの最北にあるキングの居城に到着すると、アスカの部下と合流する。彼らが囮となっている間にマイクは敷地内に進み、キングと対峙する。キングは大勢の部下をけしかけてマイクを殺害しようとするが、マイクは全員を払いのける。最後は一対一となるが、マイクの気迫が上回り、キングは白旗を揚げる（Assault Joint）。
いよいよ街を離れる時が来る。キングとの大立ち回りにより、リバティーシティ中の警察がマイクを狙っており、道路を使ってこの街を離れることはできそうもなかった。そんな時、シスコの飛行機が空港に残されていることを思い出す。マイクは命からがら飛行機にたどり着くと、エイトボールを救えなかったことを悔いながら、リバティーシティを発った（Freedom Flies）。
Grand Theft Auto Advance - 完 -