In this paper, a novel optimal charging algorithm for lithium-ion batteries is proposed to optimize constant current charging strategy with the target of minimizing temperature increment. First, a battery temperature model is established along with the identified parameters. Then, battery charging problem is formulated and solved by genetic algorithm (GA). Various charging ambient temperatures are adopted to comprehensive testify the proposed algorithm. Experimental results show that the proposed algorithm can attain satisfactory performance with the slightly shortened charging time and can reduce the temperature increment by 42.6%-93.7% compared with the constant current charging strategy.