Terrorism is a serious threat for contemporary democracies. Air traffic represents an area especially exposed to potential terrorist threats. In order to combat terrorism, the governments are ready to use different means, among them collection, mining and storage of personal data of the individuals. Following the US example, a frontrunner in this area, the EU is preparing a new system of data exchange related to passenger name record (PNR). This should come as no surprise, since almost every terrorist plan involves, in one way or another, air travel. With the aim of establishing more security in air travel, the US and the EU signed a series of agreements dealing with exchange of personal data after the US insisted that such an exchange could enhance the possibility of combating terrorism. Here the EU follows a more cautionary approach, insisting that any antiterrorist policy must respect human rights, especially here, the right to passenger privacy. Nevertheless, the EU often goes beyond what is legally permissible and encroaches into the privacy of the individuals.