Go to
this page and print out the map. Go to each of the locations and see if you can ind a red balloon. Sometimes, the balloon is put in a high or hard-to-see location, so make sure you look hard. If you look hard, but still can't find the balloon, it means you have already found the balloon, and it is time for you to move on.
To make things easy for you the next time you start a new tank, here is the amount of red balloons per district:
Vice City Mainland Viceport (4)
Escobar International Airport (4)
Little Havana (7)
Fort Baxter Air Base (2)
Starfish Island (2)
Little Haiti (10)
Downtown Vice City (18)
Vice City Beach Prawn Island (4)
Vice Point (Including Vice Point Mall) (23)
Ocean Beach (15)
Leaf Links (1)
Washington Beach (9)