Per mantenere Carl Johnson in ottima forma bisogna bilanciare due fattori: gli esercizi e la quantità di cibo. Questi due fattori sono controllati attraverso tre statistiche: Grasso, Muscoli e Nutrizione (quest'ultima è nascosta, quindi non visibile al giocatore).
Grasso e Muscoli sono due proprietà che possono aumentare e diminuire insieme o in modo opposto, nonostante il fatto che l'aumento dei muscoli causa una perdita di grasso accumulato. Si può "modellare" il nostro alter ego a nostro piacimento, per esempio avendo una barra Muscoli al massimo ma un po' di grasso nelle ossa che rappresenta probabilmente la situazione ideale per CJ.

Di solito è possibile riempire completamente la barra dei Muscoli in sole tre o quattro visite in palestra.
Le attrezzature da usare in palestra per allenarsi e fare muscoli, sono pesi e panca. Appena ci avvicineremo a questi ci apparirà un messaggio chiedendoci di premere un tasto per inziare gli allenamenti e nel menu che apparirà dovremo scegliere la quantità di peso da usare, che va dai 10 ai 44 Kg per i Pesi e dai 20 ai 160 Kg per la Panca. Naturalmente se il nostro personaggio ha la barra Muscoli al minimo, sarà opportuno scegliere un peso più leggero, poichè sarà impossibile iniziare con pesi maggiori ai 50 Kg.

Come accade nella realtà, per creare dei muscoli da zero sarà necessario esercitarsi gradualmente. Le sessioni di allenamento, man mano che si diventa più muscolosi, diventeranno più corte usando sempre la massima quantità di peso consentita.

E' importante tener conto della propria forma. I muscoli rappresentano una buona quantità di percentuale per le statistiche Sex appeal e Rispetto, è anche vero che bisogna trovare un buon rapporto muscoli/agilità/grasso per avere CJ in ottima forma e con il massimo delle performance. Aumentare la barra dei muscoli e/o del grasso al massimo comporterà una perdita di agilità nei movimenti, come correre, pedalare e nuotare, quindi bisogna trovare un'equilibrio tra massa muscolare e peso.

Si può perdere peso utilizzando due attrezzature: la cyclette e il tapis roulant. Ognuno offrirà la scelta di 10 livelli prima di iniziare una sessione di allenamento (è consigliato iniziare sempre dal primo per poi procedere man mano con gli altri livelli).
La palestra, comunque, non e' l'unico luogo in cui ci si puo' allenare, ottimi esercizi fisici possono essere anche le attività "quotidiane", tra cui il nuoto, la corsa o l'andare in bici.

Spesso la perdita di muscoli non è causata dalla mancanza di attività fisica, ma dalla nutrizione. L'elemento chiave da ricordare è che CJ ha la statistica Nutrizione che "lavora" di nascosto; se per esempio si corre troppo, il corpo di CJ inizierà a metabolizzare gli elementi costitutivi allo scopo di creare energia, quindi correre a lungo senza mangiare, causerà in CJ la perdita prima di grasso e conseguentemente di muscoli, per poi passare alla diminuzione della salute e ultimare con un decesso per denutrizione.

Oltre alla possibilità di "modellare" il nostro alter ego, si potrà anche scegliere uno dei tre stili di combattimento offerti dalle palestre sparse per tutto lo stato di San Andreas, infatti frequentando queste palestre si potranno imparare nuove mosse che si sostituiranno a quelle base.
Per apprendere nuove mosse bisogna posizionarsi sopra il cerchio rosso accanto all'istruttore della palestra, combattere contro esso e se in caso di vittoria l'istruttore ci insegnerà un nuovo stile di combattimento che varierà da palestra in palestra.
Sconfiggerlo non è difficile, basta mirare l'istruttore e poi premere i pulsanti azione fino a che non cade a terra. Appena sarà a terra, continuate a colpirlo quando tenta di rialzarsi. E' obbligatorio visitare tutte e tre le palestre e battere tutti gli istruttori affinchè si apprendano i nuovi stili di combattimento per guadagnare punti percentuale per il completamento del gioco, infatti, nonostante l'allenarsi in palestra e imparare nuovi stili di combattimento possono sembrare funzioni aggiuntive di GTA:SA, queste sono invece necessarie per completare il gioco al 100%.

Tutte e tre le palestre di San Andreas saranno disponibili dopo aver completato la terza missione affidata da Sweet: Drive-Thru.

Zona: Ganton (Los Santos)
Stile di combattimento: Boxe


Combattendo sul ring, CJ imparerà una varietà di metodologie pugilistiche che includono l'attacco in corsa, pugni a terra e combo.

Zona: Garcia (San Fierro)
Stile di combattimento: Arti marziali


In questo dojo CJ potrà imparare una nuova serie di mosse basate sulle arti marziali.

Zona: Redsands East (Las Venturas)
Stile di combattimento: Combattimento da strada


In questa palestra malandata CJ imparerà il combattimento da strada con delle dannose mosse sotto la cintura.

Zona: Mulholland (Los Santos)
Stile di combattimento: -


All'interno della villa di Madd Dogg c'è una spaziosa palestra con tutte le attrezzature per allenarsi e un campetto da basket.

Zona: Verona Beach (Los Santos)
Stile di combattimento: -


Una piccola palestra all'aperto che comprende una panca, i pesi e una cyclette. Ottima per sfoggiare il proprio fisico palestrato ai bagnanti.