This paper proposes an optimal coordinated method for electric vehicles (EVs) participating in frequency regulation (FR) under different power system operation states (PSOSs). In the proposed methodology, the FR power of EVs and generators is coordinated with different optimization objectives for power system secure and economic operations. When a power system operates in normal state, the minimum FR cost is used as an optimization objective considering the battery degradation cost. In the abnormal state, the minimum frequency restoring time is considered in the optimization objective. Based on the optimized results in different scenarios, the output power coordinated control rule between EVs and generators is drawn. Simulations on an interconnected two-area power system have validated the superiority of the proposed optimized coordinated control strategy.