Az új generáció új történetet kíván, melynek köszönhetően a Rockstar Games teljes mértékben felhagyott az előző részekben megismert alapsémával. Itt már egyáltalán nem arról van szó, hogy főszereplőnk keze alá hajtsuk a város teljes uralmát, valamint milliós értékű összegeket gyűjtsünk össze vele. A sztori sokkal inkább arról szól, hogy hogyan tehet egy embert teljes mértékben tönkre egy olyan álom kergetése, mely bizonyos okokból nem nagyon válik lehetségessé…

Főszereplőnk Nikolai Bellic, egy kelet-európai bevándorló, kit unokatestvére Roman, "amerikai álommal" kapcsolatos hazugságai, valamint a balkán háborúban csapatát csapdába csaló egyik szökevényen való bosszúállás hajt Liberty City-be. A városba történő megérkezésekor egyből szembetűnővé válik számára, hogy a fivére által emlegetett gyönyörű nők, sportkocsik és a luxusvilla egy olyan álom, melynek teljes mértékben az ellenkezője valósult meg. Roman valójában igen nagy adósságokat halmozott fel a Nagy Alma legnagyobb bűnözőivel szemben, melyet legfőképp szerencsejáték-függőségének köszönhet, és tudja, hogy csak és kizárólag Niko segíthet neki elintézni ellenségeit.

A történet során főszereplőnk rájön arra, hogy a város már önmagában képes tönkre tenni az embereket, melynek köszönhetően fontos barátai halnak meg, vagy fordulnak ellene. A játék folyamán arra is fény derül, hogy a "Szabadság Városa" túl kicsi a meneküléshez...