Vice City henter mye av sin inspirasjon fra 1980-tallets amerikanske kultur. Spillet er satt til 1986 i Vice City, en oppdiktet by modellert etter Miami. Spillets utseende, spesielt klær og kjøretøyer, reflekterer (og noen ganger parodierer) sin egen setting på 1980-tallet. I motsetning til den mørke, urbane byen i Grand Theft Auto III, Liberty City, ser Vice City (hovedsakelig) ren og pen ut, med gylne strender, svaiende palmer og livaktige solnedganger.
Historien dreier seg rundt mafia-medlemmet Tommy Vercetti, som nylig har sluppet ut fra fengsel. Etter å ha vært involvert i en narkotikahandel som gikk fryktelig galt finner Tommy de ansvarlige, mens han bygger opp et kriminelt imperium, og prøver og ta makten fra de andre kriminelle organisasjonene i byen. Spillet går ut på å bygge seg opp igjen og betale tilbake det han skylder mafiasjefen.
Kjente skuespillere har også bidratt med stemmer til spillet, f.eks. Philip Michael Thomas (Kjent som Ricardo Tubbs i Miami Vice) som Lance Vance og William Fichtner som den ganske så nervøse advokaten til Vercetti.
