The world’s demand for fossil fuels has recently increased significantly for both transportation and electric power generating sectors. Using these resources not only results in high costs and depletion of them but also increases greenhouse gas emissions and pollution. The electric vehicle (EV) market is growing globally, aiming to face climate change due to greenhouse gas (GHG) emissions and to reduce reliance on fossil fuels. However, the long charging time of EVs and the shortage of charging outlets limits the global adoption of EVs, especially on highways where the problem of accessibility to the electricity distribution grid appears. These issues can be faced by the good planning of charging infrastructure. However, this planning is a multidisciplinary field that includes electricity generation, transportation networks, EVs’ characteristics, and driver behavior. A methodology to provide the optimal locations and sizing of electric vehicle charging stations with their own electricity generation and storage using photovoltaic (PV) and energy storage systems on highways considering different factors is proposed in this paper. This paper takes a section of the western desert highway in Egypt connecting Assiut and Cairo cities as a case study. Four scenarios are proposed for the design of EV charging stations’ locations and sizing which are centralized charging stations, two-way charging stations, utilizing oil stations’ locations, and distributed fixed sizing charging points with a comparison between them. The work also discusses the potential effects of highway slope, wind speed, and number of passengers on the location problem. The results can be used to optimize the design of EV charging stations along highways for a completely sustainable system.