Under the challenge of climate change, fuel-based vehicles have been receiving increasingly harsh criticism. To promote the use of battery electric vehicles (BEVs) as an alternative, many researchers have studied the deployment of BEVs. This paper proposes a new method to choose locations for new BEV charging stations considering drivers’ perceived time cost and the existing infrastructure. We construct probability equations to estimate drivers’ demanding time for charging (and waiting to charge), use the Voronoi diagram to separate the study area (i.e., Shanghai) into service areas, and apply an optimization algorithm to deploy the charging stations in the right locations. The results show that (1) the probability of charging at public charging stations is 39.6%, indicating BEV drivers prefer to charge at home; (2) Shanghai’s central area and two airports have the busiest charging stations, but drivers’ time costs are relatively low; and (3) our optimization algorithm successfully located two new charging stations surrounding the central area, matching with our expectations. This study provides a time-efficient way to decide where to build new charging stations to improve the existing infrastructure.