Cognitive radio networks (CRNs) benefit from several features, such as decision-making, spectrum-awareness and reconfigurability over heterogeneous channels. After a link failure due to the appearance of primary users or if the channel quality becomes unacceptable, these features enable CRNs to perform a spectrum migration to a new channel to recover the transmission. In this paper, we propose a general hierarchical recovery model in which the heterogeneous channels are classified based on their parameters into distinct sets. Instead of performing a flat channel search over all channels, the CRN first selects a channel set and then performs a spectrum migration over the selected set to complete the channel search. The focus of this research is the decision procedure for selecting the best channel set to perform the recovery mechanism based on the CRN’s current state and its knowledge concerning the different channel parameters. A general dynamic decision model is proposed to find the optimal solution to this problem. Additionally, we present three decision-making heuristic algorithms. Numerical and simulation results are provided to illustrate the significant benefits of the optimal and heuristic decision algorithms for channel recovery over heterogeneous channels.