A novel valley-filling strategy for centralized coordinated charging of electric vehicles (EVs) is proposed. The proposed strategy can handle coordinated charging of millions of EVs very efficiently. The proposed strategy can alleviate the elevated peak loads of power grid arising from EV charging significantly. The proposed strategy provides much lower computational complexity than its existing counterparts.