The incorporation of electric vehicles in city logistics has become a topical issue in the last few years. Several companies and municipalities, either voluntarily or to comply with legal requirements, will need to transition to greener fleets in the next decades. Such transitions are often established by temporal targets, which dictate the number of electric vehicles that should be in the fleet by a given time period. In this research we introduce optimization-based decision making tools to support this transition. More precisely, we present a fleet replacement problem which allows organizations to determine vehicle replacement plans that will respect their fleet electrification targets in a cost-effective way. We refer to this problem as the electric fleet transition problem (EFTP). The EFTP incorporates several features that have not been considered in previous fleet replacement studies for electric vehicles, notably: temporal electrification targets, decisions regarding charging infrastructure-related investments and costs, and aggregated task assignment decisions. We formulate the EFTP as an integer linear program, and we conduct computational experiments in order to draw managerial insights regarding the impact of several features on optimal transition plans.