Limited range of electric vehicles is still a huge barrier compared to conventional vehicles. A well-established charging station network, which is derived from users’ charging demand, facilitates the spread of electric vehicles and lessens the range anxiety. Several methods have been developed for locating fast-charging stations along national roads in Europe according to the given objective function. In this paper, an arc-based location optimisation method realized by using a geographic information system and greedy algorithm is presented. An ‘oil stain’ deployment strategy is used to achieve even coverage with the minimum number of fast-charging stations along the roads. Several demographic, neighbourhood, and transport-related attributes, as well as the available services that influence the utilization of a fast-charging station, have been identified and their effects have been revealed in a systematic approach. The developed multi-criteria decision-making method has been applied to evaluate the rest areas along motorways and main roads and to propose deployment locations for fast-charging stations. The method was applied for Hungary as a case study and validated using real origin-destination (O-D) data. By the application of the locating method, the user can specify a network character by geographic parameters. The method can be especially beneficial if the O-D flows are unknown. Furthermore, the even distribution of the stations contributes to the high utilization of the fast-charging stations.