Electric vehicles’ (EVs) technology is currently emerging as an alternative of traditional Internal Combustion Engine (ICE) vehicles. EVs have been treated as an efficient way for decreasing the production of harmful greenhouse gasses and saving the depleting natural oil reserve. The modern power system tends to be more sustainable with the support of electric vehicles (EVs). However, there have been serious concerns about the network’s safe and reliable operation due to the increasing penetration of EVs into the electric grid. Random or uncoordinated charging activities cause performance degradations and overloading of the network asset. This paper proposes an Optimal Charging Starting Time (OCST)-based coordinated charging algorithm for unplanned EVs’ arrival in a low voltage residential distribution network to minimize the network power losses. A time-of-use (ToU) tariff scheme is used to make the charging course more cost effective. The concept of OCST takes the departure time of EVs into account and schedules the overnight charging event in such a way that minimum network losses are obtained, and EV customers take more advantages of cost-effective tariff zones of ToU scheme. An optimal solution is obtained by employing Binary Evolutionary Programming (BEP). The proposed algorithm is tested on IEEE-31 bus distribution system connected to numerous low voltage residential feeders populated with different EVs’ penetration levels. The results obtained from the coordinated EV charging without OCST are compared with those employing the concept of OCST. The results verify that incorporation of OCST can significantly reduce network power losses, improve system voltage profile and can give more benefits to the EV customers by accommodating them into low-tariff zones.