The smart city is an ecosystem that interconnects various devices like sensors, actuators, mobiles, and vehicles. The intelligent and connected transportation system (ICTS) is an essential part of this ecosystem that provides new real-time applications. The emerging applications are based on Internet-of-Things (IoT) technologies, which bring out new challenges, such as heterogeneity and scalability, and they require innovative communication solutions. The existing routing protocols cannot achieve these requirements due to the surrounding knowledge supported by individual nodes and their neighbors, displaying partial visibility of the network. However, the issue grew ever more arduous to conceive routing protocols to satisfy the ever-changing network requirements due to its dynamic topology and its heterogeneity. Software-Defined Networking (SDN) offers the latest view of the entire network and the control of the network based on the application’s specifications. Nonetheless, one of the main problems that arise when using SDN is minimizing the transmission delay between ubiquitous nodes. In order to meet this constraint, a well-attended and realistic alternative is to adopt the Machine Learning (ML) algorithms as prediction solutions. In this paper, we propose a new routing protocol based on SDN and Naive Bayes solution to improve the delay. Simulation results show that our routing scheme outperforms the comparative ones in terms of end-to-end delay and packet delivery ratio.