The advancements in hardware technologies have driven the evolution of vehicular ad hoc networks into the Internet of Vehicles (IoV). The IoV is a decentralized network of IoT-enabled vehicles capable of smooth traffic flow to perform fleet management and accident avoidance. The IoV has many commercial applications due to improved security and safety on the roads. However, the rapidly increasing number of wireless applications have challenged the existing spectrum bands allocated to IoV. The IoV has only six communication channels that are congested during the peak hours. The limited number of channels and the presence of congestion on these channels are the challenging issues that affect the safety of vehicles on the road. To mitigate the congestion, Cognitive Radio (CR) can be an optimal solution for the existing IoV Paradigm. In this paper, we propose a secured and efficient communication scheme for a decentralized CR-based IoV (CIoV) network. In this scheme, the Roadside Unit (RSU) senses the spectrum using an energy detection method. Each vehicle independently predicts the Primary User (PU) activity pattern using a hidden Markov model (HMM). Once a vehicle detects a licensed channel free from the PUs, it informs the RSU to store the channel in a database alongside the dedicated direct short-range communication (DSRC) channels for data transmission. The RSU and vehicles are registered with a trusted authority and they mutually authenticate each other. Upon mutual authentication, the RSU assigns communication channels to the vehicles on the road, based on their density. When the density of the vehicles is high, the detected licensed channels are used, otherwise, the DSRC channels are used. We evaluate the performance of CIoV in terms of packet delivery and packet loss ratio, end-to-end delay, and throughput, using NS-2. The simulation results show that the CR-based approach of CIoV outperforms the existing schemes and significantly enhances the performance of the underlying network.