Veiksmas vyksta [[1998]] m., mieste Liberty City, tristrejus metus iki Grand Theft Auto III įvykių. Toni Cipriani grįžta atgal į Liberty City iš [[Vice City]] po įvykdytos žmogžudystės ir sužino, kad jis jau nelabai gerbiamas mieste ir jo pareigas Leone šeimos mafijoje užima kitas žmogus. Tada Toni bandydamas grąžinti savo pagarbą iš kitų, vėl pradeda dirbti donui Leone Salvatore, padeda jam kariauti su kitų šeimų mafijomis, saugo Leone šeimą ir dar padeda grąžinti senas Leone mafijai priklaususias teritorijas. Toni šio laikotarpio metu rūko psichotropines medžiagas, žaidžia azartinius žaidimus, vagia automobilius ir žudo žmones.
Kai mafijų karai aprimo ir Toni jau yra gerbiamas, jis su savo mama nusiperka restoraną "Cipriani's Ristorante" ir ramiai sau gyvena.
