The European Parliament has approved a joint system for police and justice officials to access airline passenger data on all flights to and from the EU.
The measure was passed by 461 votes to 179 against.
Counter-terrorism officials have lobbied for years for the introduction of Passenger Name Records, arguing that sharing data will help them trace suspicious itineraries.
EU countries will have two years to turn it into national law.
The data in question is already collected by airlines but the new legislation sets out detailed rules for national authorities to access it when tackling serious crime.
Support for data monitoring
Gun and bomb attacks by the Islamic State-IS group in Paris last year and Brussels this year have boosted support for such data monitoring in the EU.
The European Commission welcomed the vote, calling it a “strong expression of Europe’s commitment to fight terrorism and organised crime”.
France’s Interior Minister Bernard Cazeneuve said in a statement that the new system would be a “precious tool to strengthen the security of European citizens”.
“Passenger Information Units”-PIUs will be set up in each member state to store data.
The text of the new measure rules out any processing of data revealing a person’s race or ethnic origin, religion, political opinion, trade union membership, health or sexual life.
PIUs will be obliged to delete any such data if they receive it.
The new system will still require the approval of the European Council, which represents member states.