In this article, we examine the European framework of collecting and analysing flight passenger name record (PNR) data for the purpose of combating terrorism and serious crime. The focus is mainly on the EU PNR Directive of 2016, but we also consider the specific legislative framework in Germany and Denmark. In light of the upcoming review process for the Directive, the article aims at exploring the policy-related, legal and technological challenges. In doing so, it will go beyond established data-protection concerns. In particular, we examine the legal and conceptual challenges that new technology may bring for the exercise of police authority. This article also debunks the popular claim that PNR analysis in and of itself entails the risk of algorithmic discrimination of certain groups, which is often associated with AI-driven predictive policing. Moreover, it provides useful insights into the specific legal safeguards vis-à-vis automated profiling through human review.