This paper examines and optimizes parameters that affect the air cooling of a Lithium-Ion (Li-Ion) battery, used in Electric Vehicles (EVs). A battery pack containing 150 cylindrical type Li-Ion battery cells in a PVC casing is investigated. An equal number of tubes are used in the pack as a medium to cool the battery by using a fan when the vehicle is stationary or with ambient air when in motion. The parameters affecting the air cooling of battery are studied and optimized by considering their practical constraints. The objective function and Number of Transfer Unit (NTU) are developed. Finally, a genetic algorithm method is employed to optimize the decision variables. Analysing the results shows that NTU can be maximized by increasing the diameter of tubes on the battery and keeping the air velocity in a certain range.