Electricity is now considered as the ultimate alternative against the internal combustion engines by automotive industry while strict regulations for the emission of CO2 have also exploited vehicles’ electrification. Unfortunately, the effort put on the study of the wide use of electric vehicles is limited. The arisen issue deals with the size of an EV fleet while it is rather expected that the environmental benefits of a wide use will vary with location, performance, and condition of the vehicles as well as electricity production mix and the electricity supply network. This work simulates the electrification of the fleet of private cars in Greece, which seems to be ultimate case study. The Greek market of both conventional and electric vehicles was analyzed as for sales per segment per year. Several portions of replacements have been considered for conventional private cars with EVs, under several scenarios of everyday use. The costs of this use have also been studied under several scenarios. A strong dependence of carbon dioxide emissions on the fleet size and the source used for electricity production is found, where the wide use of EVs is proven not currently cost beneficial, especially for non-urban use.