Fast charging stations (FCSs) can facilitate the uptake of Electric Vehicles (EV), but their installation requires significant investments affecting their profitability. An optimal determination of charging locations and capacities based on associated costs can help to provide infrastructure efficiently. As initial FCSs affect installations and costs in later years, a strategic infrastructure development plan over multiple years is required to expand the infrastructure to satisfy the charging demand of a growing EV fleet, while pursuing the goal of minimal costs. Based on former work, a model for the investment-optimal allocation and sizing of FCSs over multiple years (including costs for grid connection) is developed. For the first time, a multi-periodic capacitated Arc-Cover Path-Cover formulation with an investmentoptimal objective is proposed and applied to New Zealand. The results are analyzed with respect to the locations and sizes of FCSs, the impact on the coverage of traffic flows, and the related trends over time. They indicate that FCSs are to be located along highly trafficked corridors in densely populated regions for being applied profitably. The chosen station locations have below-average installation costs and are capable of covering high shares of EV traffic on inter-regional and highly frequented routes.