There is increased interest in deploying charging station infrastructure for electric vehicles, due to the increasing adoption of such vehicles to reduce emissions. However, there are a number of key challenges for providing high quality of service to such vehicles, stemming from technological reasons. One of them is due to the relative slow charging times and the other is due to the relative limited battery range. Hence, developing efficient routing strategies of electric vehicles requesting charging to stations that have available charging resources is an important component of the infrastructure. In this work, we propose a queueing modeling framework for the problem at hand and develop such routing strategies that optimise a performance metric related to vehicles’ sojourn time in the system. By incorporating appropriate weights into the well-known dynamic routing discipline “Join-the-Shortest-Queue”, we show that the proposed routing strategies not only do they maximise the queueing system’s throughput, but also significantly mitigate the vehicle’s sojourn time. The strategies are also adaptive in nature and responsive to changes in the speed of charging at the stations, the distribution of the vehicles’ point of origin when requesting service, the traffic congestion level and the vehicle speed; all the above are novel aspects and compatible with the requirements of a modern electric vehicle charging infrastructure.