Abstract: The Internet of vehicles (IoV) is increasingly being used to realize the vision of intelligent transportation systems with the rapid development of computation and communication technologies. However, numerous IoV applications rely on a central unit for storing and processing information and mediators for wireless transmission. This can lead to the leakage of sensitive data and high costs and delays. To address these issues and improve the efficiency of data storage, processing, and sharing in the IoV, we propose a vehicle-based secure blockchain consensus (VBSBC) algorithm. Our VBSBC algorithm overcomes the limitations and drawbacks of state-of-the-art approaches by leveraging blockchain technology and a consensus algorithm to ensure secure communication between vehicles. In addition, the algorithm includes an authentication process and a key distributing and request process, illustrated during vehicles’ movement between different zones. In simulation results, our proposed VBSBC algorithm demonstrated high performance compared to existing approaches in terms of authentication delay, key processing time, attack detection rate, throughput, and packet loss rate.