To fully realize the potential of autonomous aerial vehicles, a reliable, robust, and accurate navigation system is required. Current technologies composing such a system include stand-alone and augmented global navigation satellite systems (GNSS), as well as visual, inertial, and signals-of-opportunity (SOPs) approaches. However, as it is well understood that no single alternative can meet the requirements for full autonomy, a combination of technologies is required to address alternative application scenarios. In this work, an online technique for relative positioning of autonomous unmanned aerial vehicles (UAVs) is proposed that capitalizes on SOPs in conjunction with inertial measurements for localization and navigation when GNSS signals are not readily available. The proposed system uses the signals’ characteristics over a large part of the frequency spectrum, in conjunction with an optimal learning (OL) technique, to adaptively choose a sequence of frequencies that provide location estimates in real-time. Subsequently, inertial measurements, which are provided by an onboard unit, are employed to improve on the tracking accuracy. Field experiments, using an autonomous unmanned aerial vehicle, demonstrate the effectiveness of the proposed solution under various parameter settings.