Story
完全なネタバレなので、クリアしてから見てください。
プロローグ
1986年のリバティーシティ。
マルコ'sビストロの薄暗い店内で男たちが会話をしている。
「トミー・ベルセッティが出所しただと？」
男たちにとって、彼の15年ぶりの出所は歓迎されないもののようだ。ソニーという名の男は、トミーを南国のバイスシティに厄介払いする底企みをひけらかす。彼らのファミリーはドラッグには手を出していないが、誰かに手を汚させてビジネスを拡大する計画のようだ。もちろん、儲けは自分たちの手中に収める腹積もりである。トミーの監視役として、ケン・ローゼンバーグ（Ken Rosenberg）というお抱え弁護士の名前が挙がる。
トミー・ベルセッティ
場面はバイスシティのエスコバル国際空港に変わる。
ケン・ローゼンバーグは、白いセダンで訪問者を歓迎する。本作の主人公であるトミー・ベルセッティ（Thomas "Tommy" Vercetti）と、もう2人の部下が車に乗り込む。ケンは取引場所に向かう道中、今回のドラッグ取引の内容を意気揚々と語る。
車は人けのないバイスポートの港に到着する。間もなくして取引相手のヘリが降下してくる。ケンを車に残し、トミー達は車を降りていく。取引相手も巨大なアタッシュケースを持ってヘリを降りてくる。トミー達は用意したカネを相手に確認させ、取引は成立しそうに見えた。
その瞬間、激しい銃声がとどろく。取引を狙って何者かが待ち伏せをしていたのだ。トミーは銃弾を何とか回避したものの、他の者は命を落としてしまう。ブツもカネもその場に残したまま、トミーとケンは命からがらその場を離れることしかできなかった。
バイスビーチにあるケンの事務所前に戻ってきた二人は、簡単に明日の約束をすると解散となった。
宿泊先のホテルに戻ってきたトミーはソニーに電話をかける。会話をするのは15年ぶりである。ソニーは白々しくもトミーを思いやっているかのようにふるまう。しかし、取引の首尾を伝えられたソニーは激怒する。最後のチャンスとしてブツとカネを取り戻すことをトミーに約束させ、電話を切る。
トミーは受話器を床にたたきつける（An Old Friend）。
ケンの事務所
ケン・ローゼンバーグ
トミーはケンの事務所を訪れる。ケンは昨日の事件を受けてすくみ上っていたが、トミーはそれをなだめる。ケンは、元大佐のファン・ガルシア・コルテス（Colonel Juan Garcia Cortez）のことを思い出す。彼は今回の取引の手引きをしてくれた人物で、ちょうど船上パーティを催しているらしい。事件の手掛かりを得るべくトミーは立ち上がる。
パーティ会場では、コルテス大佐が迎える。彼も事件のことは把握しており、調査を進めているという。ここで、大佐の娘であるメルセデス・コルテス（Mercedes Cortez）が紹介される。大佐はメルセデスを残してその場を離れる。
メルセデスは立ち話がてら他の客のことを教えてくれる。アレックス・シュラブ議員とその愛人キャンディ・サックス、元アメフトのスター選手BJスミス、ロックバンドラブフィストのヴォーカルであるジェズ・トレント、ゴンザレス、リチャード牧師、映画監督のスティーブ・スコットなどなど。後で思えば特異点ともいえるほどの面々が一堂に会していた。
麻薬王リカルド・ディアス（Ricardo Diaz）がコルテス大佐と親しげに会話をしている。メルセデスはディアスの声かけを軽くあしらうと、トミーとパーティを抜ける（The Party）。
ケンの事務所に戻ると、街をよく知る人物としてケント・ポール（Kent Paul）の名が挙がる。マリブクラブでナンパ中のポールに割り込むと、ケンのことを無実の人間を死刑にする弁護士として認識しているようだった。軽く脅しながら事件の心当たりを尋ねると、最近ワシントンビーチにいるシェフの羽振りがいいと口走る。そのシェフから情報を引き出そうとするものの、もみ合いの末殺害してしまう。ここで、白いスーツを着た謎の男が現れる。彼は先日の襲撃で命を落とした取引相手の弟であるという。目の前で手掛かりを殺害されてしまったことについて嫌味を言うが、彼は彼で調査を続けるといい、その場は解散となった（Back Alley Brawl）。
その後、ソニーのいとこの陪審員の口を封じたり（Jury Fury）、不動産王エイブリー・キャリントン（Avery Carrington）の地上げを手伝ったりする（Riot）。
ここで、コルテス大佐から連絡が入り、詳しい話をするため再び彼の船に向かう。
コルテス大佐と新たな人脈
コルテス大佐
船上では、大佐がロブスターで出迎える。先日の襲撃は、彼の部下であるゴンザレス（Gonzalez）の情報漏洩が原因であると話す。不手際を謝罪するとともに、今後の調査も約束する。トミーは、大佐から手渡されたチェーンソーでゴンザレスを真っ二つにする（Treacherous Swine）。
しばらく調査の進展が伝えられないまま、とあるチップを運び屋から受け取ったり（Mall Shootout）、リカルド・ディアスの取引の護衛をすることになったりする。武器が隠されている立体駐車場に行くと、例の白スーツの男と鉢合わせする。名前はランス・ヴァンス（Lance Vance）というらしい。二人でディアスの護衛を行うことになる。取引は襲撃に遭うが、ディアスとカネを守り切ることに成功する。この働きにより、ディアスから感謝を得るとともに、彼の記憶に留められることになる（Guardian Angels）。
ディアスへの接近
リカルド・ディアス
早速ディアスから呼び出しがかかる。彼はスターフィッシュ島の大豪邸に居を構えている。
ディアスはトミーをパートナーではなく、あくまで手下として使いたいようだ。トミーの意見は聞かずに一方的にまくしたてる。ディアスを裏切った人物の潜伏先を特定する仕事を指示される（The Chase）。続いて、その潜伏先をヘリで襲撃するように指示される。この仕事には、「クエンティン」という偽名でディアスの懐に入り込んでいるランスも参加する。彼は、襲撃事件の首謀者はディアスであると確信しているようだ。二人のチームワークにより、襲撃は成功裏に終わる（Phnom Penh '86）。
麻薬密輸用の最速のボートを盗み（The Fastest Boat）、その速度を生かして麻薬の取引に一番乗りするように指示される。このミッションには、またまたランスが参加する。ディアスとの仕事を続ける理由についてトミーは、この街を知るためであると答える（Supply & Demand）。
再びコルテス大佐から呼び出される。大佐もまた襲撃事件の黒幕はディアスであると思いなしていた。それはそれとして、街を走行中の戦車を奪い取ることを指示される。軍の車列がドーナツ店に寄った隙をついて強奪に成功する（Sir, Yes Sir!）。
ランスが死んじまう！？
ケント・ポール
突然、ポールから呼び出しがあり、マリブクラブに急行する。ランスがディアスを襲撃したものの、返り討ちに遭い、廃品置き場に拘束されているという。トミーは廃品置き場に急行する。大勢のディアスの手下をなぎ倒して進むと、最奥部に瀕死のランスがいた。トミーは先走って行動したランスを咎めはしたが、トミーの中でも決意は固まったようだ。ひとまずランスを病院に送り、彼の回復を待つことになる（Death Row）。
脱出
コルテス大佐は、先日奪取したチップが原因でフランス当局から追い詰められていた。飛行機で逃亡するには荷物が多いため、大佐の大型ヨットをアシにすることになる。ヨットが出航すると、当局のエージェントが激しい攻撃や進路妨害を仕掛けてくる。トミーは一騎当千の働きを見せ、敵を退ける。大佐は別れ際に娘を任せるといい、祖国に向けて舵を切った（All Hands On Deck!）。
復讐の時
ディアス邸のそばで待っていると、ランスが車で現れる。トランクにはトミーがドン引きするほどの武器が格納されていた。
ディアスもこの襲撃に気づく。大量の防犯モニターで二人の姿を確認すると武器を手にする。
屋敷内にいるディアスに向けて進軍するトミーとランス。ディアスの手下の激しい抵抗を押しのけて進むと、広い階段ホールに到着する。そこにディアスが姿を現す。ディアスは「裏切者」とトミーをののしるが、トミーは冷静に数十発の弾丸を命中させる。たまらず書斎に引き下がるディアスだが、さらに数十発の弾丸を浴びせられて床に倒れる。
仰向けで最期の悪態をつくディアスにトミーとランスが近づく。二人の拳銃がディアスの頭部に向けられた直後、あたりに銃声と閃光が広がった（Rub Out）。
主人のいなくなったディアス邸は、トミー達のものとなる。
ベルセッティ・ファミリー
新たにベルセッティ邸となった大豪邸には、トミー、ランス、ケン、エイヴリーが集まっていた。トミーは、この街を「いただく」意思を強める。ランスは、自分たちの力を街に知らしめる必要があると語る。エイヴリーは、不動産王の観点から、シノギの重要性も説明する。トミーは5分で戻ると自信満々に言い残し、邸宅を飛び出す。島の北部にある大型ショッピングモールに到着すると、ショップのウインドウを次々に破壊していく。立ち去り際に、ベルセッティの名前を言い残し、みかじめ料の支払いを要求する（Shakedown）。
ソニーから電話がかかってくる。トミーがしばらく何の連絡も寄こしていないことについて不満を述べる。ディアスの事業を乗っ取ったことはすでに知っているようだ。
みかじめ料の支払いを拒否する店が現れたときは、具体的な行動に移していなかったランスを叱責する。トミーは店に直接乗り込み、警備を担当している警備会社のメンバーを皆殺しにした（Bar Brawl）。
ランスは、自身の処遇の悪さについて不満の意を述べる。トミーは、ミスが多いためと説明するが、ランスの不満はますます増大していく。二人の間に不穏な空気が漂い始める。
ある日、ベルセッティ邸の玄関前で部下を叱責するランスの姿があった。ショッピングモールの店舗を爆破するはずが、警察への情報漏洩により失敗したという。トミーの発案により、警官に扮して現場に潜入し、証拠もろとも吹っ飛ばすことになる。首尾よく警官の制服を入手したトミーとランスは、ショップの爆破に成功する（Cop Land）。
ファミリーの拡大
トミーは、思うところがあり老朽化した印刷工場を購入する。彼の父親が印刷工であり、もともとその跡を継ぐつもりだったらしい。新聞か雑誌を印刷するつもりのトミーに対し、元オーナーがとんでもないことを口走る。どうせなら紙幣を印刷したらどうかと。ただ、そのためにはシンジケートが扱っている原版が必要だという。トミーは街の噂に詳しいポールを尋ねる。ポールの話では、船着き場にいる海運会社の船長が情報を持っているという。船着き場のコンテナ船に乗り込むと、激しい抵抗を受けるが情報を持ち帰ることに成功する（Spilling the Beans）。
入手した情報により、原版が運搬されるスケジュールが判明する。待ち伏せの末、輸送中の運び屋を襲撃し原版を入手する。持ち帰った原版を使い、元オーナーの力を借りて偽札の印刷が始まる（Hit the Courier）。
ソニーから再び電話がかかってくる。ソニーは、カネとブツをどこへやったのかと声を荒らげて詰問する。トミーは相手にせずに電話を切る。
トミーは、印刷工場以外にもいくつかの物件を買い進め、表と裏、両方の顔で資金を確保するとともに名を揚げていく。
過去の清算
非常事態が発生しているとの連絡を受け、印刷工場に急行する。工場は何者かに襲撃された後だった。負傷した工場長の口から出たソニー・フォレッリ（Sonny Forelli）の名前を聞くと、トミーの顔色が変わる。ついに奴が動き出したのだ。
ソニーの部下は、トミーが所有している物件を次々に襲撃する。トミーは、物件に寄り付いた襲撃者を片っ端から始末し、物件と収益を守った（Cap the Collector）。
トミーは本丸のベルセッティ邸に下がり、ランスらと作戦会議を行う。ランスの話では、ソニーらが今日邸宅に乗り込んでくるという。トミーは迎え撃つ覚悟を決め、ケンに偽札の用意、ランスに部下の取りまとめを指示する。
ほどなくしてソニーは部下を引き連れて登場する。険悪な雰囲気の中トミーは、カネならあるといい、偽札の入ったカバンを差し出す。トミーは、例の襲撃事件の話を出しソニーを責め立てる。ソニーは、俺には関係のない話として相手にせず、ビジネスを理解してもらえず残念だと言い放つ。
続けてソニーは、ビジネスを理解してくれる者もいたと述べる。何を隠そう、ランスのことであった。ランスは、ソニーのそばに移動すると、ビジネスとしてトミーを売ったことを告白する。また、カバンの中身が偽札であることもばらしてしまう。
銃撃戦が始まる。マフィアの部下がトミーの金庫に向かって次々と前進してくるが、全員返り討ちにする。そこにランスが現れ、お前の味方はいないと叫んで逃走する。トミーはランスを屋上に追い詰めると、ラストダンスだと宣告し、ランスを殺害する。
階段ホールにソニーが現れ、お前はただの捨て駒でしかないと声を張り上げる。トミーは15年間の清算として、ソニーにありったけの銃弾を浴びせる。戦いは終わった。
物陰に隠れていたケンが姿を現し、トミーの身を気にかける。ランスについてはケンも毛嫌いしていたようで、死んでよかったとまでいう。トミーは、これでリバティーシティからの干渉はなくなり、美しいビジネスの始まりだと胸を張る。
トミー・ベルセッティは新たな一歩を踏み出した（Keep Your Friends Close...）。
Grand Theft Auto: Vice City - 完 -
冒頭の襲撃事件で死亡した取引相手は、GTA:VCSの主人公ヴィクター・ヴァンス（Victor Vance）です。どういうわけか、容姿や立ち居振る舞いが全く違う人物になってしまっています。