In this paper, a new passive thermal management system for electric vehicles is developed. A latent heat thermal energy storage with nanoparticles is designed and optimized. A genetic algorithm method is employed to minimize the length of the heat exchanger tubes. The results show that even the optimum length of a shell and tube heat exchanger becomes too large to be employed in a vehicle. This is mainly due to the very low thermal conductivity of phase change material (PCM) which fills the shell side of the heat exchanger. A carbon nanotube (CNT) and PCM mixture is then studied where the probability of nanotubes in a series configuration is defined as a deterministic design parameter. Various heat transfer rates, ranging from 300 W to 600 W, are utilized to optimize battery cooling options in the heat exchanger. The optimization results show that smaller tube diameters minimize the heat exchanger length. Furthermore, finned tubes lead to a higher heat exchanger length due to more heat transfer resistance. By increasing the CNT concentration, the optimum length of the heat exchanger decreases and makes the improved thermal management system a more efficient and competitive with air and liquid thermal management systems.