In this paper, we investigate the performance gains of cognitive radio relay networks under delay quality of service (QoS) limitations at the secondary users, and spectrum-sharing restrictions imposed by the primary users of the channel. In particular, we assume that the primary user allows secondary users to gain access to its allocated spectrum band as long as a certain threshold on its corresponding outage probability is satisfied. Using this constraint, we find the maximum limit on the interference-power inflicted on the primary receiver that should not be exceeded by the transmission of the secondary users. In addition, we assume that the secondary transmitter benefits from an intermediate node, chosen from K terminals, to relay its signal to the destination. Considering that the transmission of the secondary user is subject to satisfying a statistical delay QoS constraint, we obtain the maximum arrival-rate supported by the secondary user's relaying link. In this respect, we derive closed-form expressions for the effective capacity of the channel in Rayleigh block-fading environment Numerical simulations are provided to endorse our theoretical results.