The Internet of Vehicles (IoVs) has become a vital research area in order to enhance passenger and road safety, increasing traffic efficiency and enhanced reliable connectivity. In this regard, for monitoring and controlling the communication between IoVs, routing protocols are deployed. Frequent changes that occur in the topology often leads to major challenges in IoVs, such as dynamic topology changes, shortest routing paths and also scalability. One of the best solutions for such challenges is “clustering”. This study focuses on IoVs’ stability and to create an efficient routing protocol in dynamic environment. In this context, we proposed a novel algorithm called Cluster-based enhanced AODV for IoVs (AODV-CD) to achieve stable and efficient clustering for simplifying routing and ensuring quality of service (QoS). Our proposed protocol enhances the overall network throughput and delivery ratio, with less routing load and less delay compared to AODV. Thus, extensive simulations are carried out in SUMO and NS2 for evaluating the efficiency of the AODV-CD that is superior to the classic AODV and other recent modified AODV algorithms.