A new methodology based on Tabu Search algorithm optimization is proposed in this paper in order to solve the plug-in electric vehicle (PEV) charging coordination (PEVCC) problem in electrical distribution systems (EDSs). The proposed method minimizes the total operational costs of the EDS by determining an optimal schedule for the charging of the electric vehicle batteries. In order to improve the efficiency of the optimization algorithm, a sensitivity index is used to approximate the power losses assessment of the charging schedule analyzed by the Tabu Search algorithm. The proposed method was used to solve the PEVCC problem in two test systems and the results shown that the achieved solution is able to operate the EDS economically while the operational constraints are satisfied.