2004. május 11-én a minden évben megrendezésre kerülő E3-on a Sony bejelenti az új kézikonzolját. 2004. december 14-én polcokra kerülnek az első PSP-k Japánban, majd következő év szeptember elsején Európába is megérkeznek az első hordozható játékgépek, de a két megjelenés között még történt egy fontos esemény: a Rockstar Games bejelentette új játékát a Liberty City Stories-t. A játék helyszíne természetesen Liberty City, mellyel már az ezt megelőző Grand Theft Auto részekben is találkozhattunk. A város ugyanúgy 3 szigetből (Portland, Staunton Island és Shoreside Vale) áll, mint a Grand Theft Auto III-ban, és csak kisebb változtatásokat tartalmaz a régebbi GTA epizódokhoz képest. A játék cselekménye 1998-ban zajlik le, 3 évvel a GTA III történései előtt.

A főszereplőnk, akit irányíthatunk nem más, mint Toni Cipriani, akit a Grand Theft Auto III-ban megismerhettünk, mint munkaadót. Sajnos a játék az előző GTA epizódokhoz képest nagyon sok visszafejlődést mutat. Több hasznos és fontos tulajdonságát is elvették főhősünknek, ilyen például, hogy nem tudunk úszni. Másik pedig, hogy nem tudunk mászni így a San Andreas-tól eltérően, nem hódíthatjuk meg az épületeket/mászhatjuk meg az előttünk akadályként álló kerítéseket.

A játék nagy újdonsága, hogy tartalmaz multiplayer funkciót. A Rockstaros srácok hosszú idő után úgy döntöttek, hogy meglepik a rajongókat egy egyszerű többjátékos móddal. A multival maximum 6 játékos játszhat egyidejűleg a PSP által használt Wi-Fi segítségével. Ezeket leszámítva a játékban szinte mindent megtehetünk, amit az előző részekben megismerhettünk, tehát a fő küldetések mellett rengeteg mellékküldetést, feladatot, és egyéb dolgot hajthatunk végre.

A Liberty City Stories néhány hátrányát leszámítva hosszú hetekig uralta a PSP-s játékok eladási listáját és még hónapokig benne volt a TOP10-ben. Ennek hatására a játék elvesztette PSP exkluzivitását és megjelent a PlayStation másik konzoljára PS2-re is. Ezáltal a játék egy újabb fénykorát élte meg. Ezek után elmondhatjuk, hogy a Rockstar Games nagyon jól járt a játék elkészítésével és talán ennek hatására készült el később a Vice City Stories.