Avian navigation has fascinated researchers for many years. Yet, despite a vast amount of literature on the topic it remains a mystery how birds are able to find their way across long distances while relying only on cues available locally and reacting to those cues on the fly. Navigation is multi-modal, in that birds may use different cues at different times as a response to environmental conditions they find themselves in. It also operates at different spatial and temporal scales, where different strategies may be used at different parts of the journey. This multi-modal and multi-scale nature of navigation has however been challenging to study, since it would require long-term tracking data along with contemporaneous and co-located information on environmental cues. In this paper we propose a new alternative data-driven paradigm to the study of avian navigation. That is, instead of taking a traditional theory-based approach based on posing a research question and then collecting data to study navigation, we propose a data-driven approach, where large amounts of data, not purposedly collected for a specific question, are analysed to identify as-yet-unknown patterns in behaviour. Current technological developments have led to large data collections of both animal tracking data and environmental data, which are openly available to scientists. These open data, combined with a data-driven exploratory approach using data mining, machine learning and artificial intelligence methods, can support identification of unexpected patterns during migration, and lead to a better understanding of multi-modal navigational decision-making across different spatial and temporal scales.