A játék története 1992-ben kezdődik, amikor is a főhős, Carl "CJ" Johnson visszatér San Andreas államába. Ezt megelőzően 5 évvel (tehát 1987-ben) a bandák közti rivalizálás oly mértékben tetőfokára hágott, hogy el kellett hagynia a térséget, így Liberty City városában próbált új életet kezdeni. Egy nap azonban jött a hír: Beverly Johnson, Carl édesanyja meghalt. Főhősünk tehát visszatér Los Santos-ba, hogy részt tudjon venni anyja temetésén.
Alighogy megérkezik a városba, egyből összetűzésbe kerül a két korrupt rendőrrel, Frank Tenpenny-vel és Eddie Pulaski-val, akik azzal zsarolják, hogy a nyakába varrják Pendelburry rendőrtiszt meggyilkolását, hacsak nem húzza meg magát. Miután a két zsaru elvette CJ maradék pénzét, a rivális banda, a Ballas területén kirakják főhősünket, mintegy "sok szerencsét" kívánva. Carl felismeri, hogy a Johnson család bandája, az Orange Grove Families már nem az, ami 5 éve volt, így arra az elhatározásra jut, hogy Los Santos-ban marad, a banda újbóli fellendítésének érdekében. Mindezt számos erőfeszítéssel és sok csalódással tudja elérni, és ehhez kapcsolódik a fő sztorivonal.
