In this paper, an optimization method is proposed to improve the efficiency of a transmission equipped electric vehicle (EV) by optimizing gear shift strategy. The idea behind using a transmission for EV is to downsize the motor size and decrease overall energy consumption. The efficiency of an electric motor varies with its operating region (speed/torque) and this plays a crucial role in deciding overall energy consumption of EVs. A lot of work has been done to optimize gear shift strategy of internal combustion engines (ICE) based automatic transmission (AT), and automatic-manual transmissions (AMT), but for EVs this is still a new area. In case of EVs, we have an advantage of regeneration which makes it different from the ICE based vehicles. In order to maximize the efficiency, a heuristic search based algorithm - Genetic Algorithm (GA) is used. The problem is formulated as a multi-objective optimization problem (MOOP) where overall efficiency and acceleration performance are optimized. A mathematical formulation is provided to calculate the maximum possible efficiency for a given drive cycle. Non-dominated Sorting Genetic Algorithm (NSGA-II) is used to optimize the gear shift lines. A comparative study of fuel economy improvement is provided to validate the concept of using different downshift lines during regeneration.