Electric vehicles (EV) are promoted as a foreseeable future vehicle technology to reduce dependence on fossil fuels and greenhouse gas emissions associated with conventional vehicles. This paper proposes a data-driven approach to improving the electrification rate of the vehicle miles traveled (VMT) by a taxi fleet in Beijing. Specifically, based on the gathered real-time vehicle trajectory data of 46,765 taxis in Beijing, we conduct time-series simulations to derive insight for the public charging station deployment plan, including the locations of public charging stations, the number of chargers at each station, and their types. The proposed simulation model defines the electric vehicle charging opportunity from the aspects of charge time window, charging demand and charger availability, and further incorporates the heterogeneous travel patterns of individual vehicles. Although this study only examines one type of fleet in a specific city, the methodological framework is readily applicable to other cities and types of fleets with similar dataset available, and the analysis results contribute to our understanding on electric vehicles’ charging behavior. Simulation results indicate that: i) locating public charging stations to the clustered charging time windows is a superior strategy to increase the electrification rate of VMT; ii) deploying 500 public stations (each includes 30 slow chargers) can electrify 170 million VMT in Beijing in two months, if EV’s battery range is 80 km and home charging is available; iii) appropriately combining slow and fast chargers in public charging stations contributes to the electrification rate; iv) breaking the charging stations into smaller ones and spatially distributing them will increase the electrification rate of VMT; v) feeding the information of the availability of chargers at stations to drivers can increase the electrification rate of VMT; and vi) the impact of stochasticity embedded in the trajectory data can be significantly mitigated by adopting the dataset covering a longer period.