Fixed relay networks will be an integrated component of future International Mobile Telecommunications (IMT)-Advanced. In this paper, we propose a new approach to relay handover and link adaptation. Our approach is built on a new Markov chain model (MCM) that comprehensively characterizes different relay protocols and quantifies their quality-of-service (QoS) measures, such as packet drop rate and latency, and spectral efficiency. Our relay handover and link adaptation scheme combats channel fluctuations while satisfying QoS requirements. It also accommodates multiple relay stations, supports multiplexing and diversity, and copes with mutually related and time-dependent transmissions. Analytical results, which were validated by simulations, show that our scheme can reduce the packet loss by up to three orders of magnitude. It also decreases the packet delay by up to 18% and improves the throughput by up to 10%.