In this article, we introduce and study a two-stage stochastic optimization problem suitable to solve strategic optimization problems of car-sharing systems that utilize electric cars. By combining the individual advantages of car-sharing and electric vehicles, such electric car-sharing systems may help to overcome future challenges related to pollution, congestion, or shortage of fossil fuels. A time-dependent integer linear program and a heuristic algorithm for solving the considered optimization problem are developed and tested on real world instances from the city of Vienna, as well as on grid-graph-based instances. An analysis of the influence of different parameters on the overall performance and managerial insights are given. Results show that the developed exact approach is suitable for medium sized instances such as the ones obtained from the inner districts of Vienna. They also show that the heuristic can be used to tackle very-large-scale instances that cannot be approached successfully by the integer-programming-based method.