Flying Ad Hoc Network (FANET) consisting of Unmanned Aerial Vehicles (UAVs) can undertake many tasks difficult for traditional Mobile Ad Hoc Networks (MANETs). However, the highly dynamic topology of FANET imposes difficulties for adopting existing MANET routing protocols. In this paper, we present the Link Stability Estimation-based Preemptive Routing (LEPR) protocol targeting FANET on the basis of AODV, an existing routing protocol for ad hoc networks. Taking advantage of GPS location information of UAVs, a new link stability metric is introduced for LEPR. This new metric uses the link quality, safety degree and mobility prediction factor to take into account the past, current and future statuses of link stability respectively. With this new metric, LEPR calculates multiple robust link-disjoint paths during the route discovery process. In addition, a semi-proactive route maintenance process is initiated when anticipating link breaks. This preemptive mechanism reduces the number of broken paths and packet latency by finding and switching to a more reliable path early. Simulation results demonstrate that LEPR significantly outperforms two popular routing protocols, AODV and DSR, in terms of packet delivery ratio, delay and routing overhead, whether in a high or low mobility setting.