The data "must only be used to prevent, detect, investigate and prosecute these crimes", the European Parliament said, as safeguards have been added to ensure "the lawfulness of any storage, analysis, transfer and use of PNR data".
PNR data can include any personal information collected during bookings for flights, including home addresses, mobile phone numbers, frequent flyer information, email addresses and credit card details.
Data protection safeguards include rules stating that national Passenger Information Units (PUIs) will only be allowed to process PNR data for specific purposes, such as identifying a passenger who "may be involved in a terrorist offence or serious transnational crime and who requires further examination", the Parliament said.
PIUs will have to appoint a data protection officer to monitor data protection and safeguards, and to act as a contact point for passengers with concerns.
All processing of PNR data will have to be logged, and passengers must be "clearly and precisely informed" about the collection of data and their rights, the Parliament said.
Stricter conditions will cover any transfer of data to third countries, it said.
Provisions prohibiting the use of sensitive data or the transfer of PNR data to private parties were also backed by MEPs.
"Without this EU system in place a number of EU governments will go it alone and create their own systems. That would leave gaps in the net and create a patchwork approach to data protection. With one EU-wide system, we can close the net and ensure high standards of data protection and proportionality are applied right across Europe. The emerging threat posed by so-called 'foreign fighters' has made this system even more essential", said Civil Liberties Committee rapporteur Timothy Kirkhope.
"PNR is not a ‘silver bullet’ but it can be an invaluable weapon in the armoury. We will now open talks with national governments with a view to reaching a final agreement before the end of the year", he said.
The rules would apply to air carriers and travel agencies and tour operators operating 'international flights' into or out of the EU, according to the committee amendments. They would not apply to 'intra-EU' flights between EU member states.
Data can be retained by the PIU for 30 days, after which all elements that could identify a passenger have to be 'masked out'. All data must be permanently deleted after five years unless it is being used in a specific criminal investigation or prosecution, the parliament said.
EU countries should use Europol's Secure Information Exchange Network Application (SIENA) system to share PNR data, it said.
The amended rules were approved by 32 votes to 27. The mandate to open negotiations with the EU Council of Ministers was approved by 36 votes to 14, with eight abstentions.
Negotiation with individual member states will have to take place before the proposal becomes law.
The PNR directive has been under discussion since it was proposed in 2011, to bring the EU into line with US, Canada and Australia. In 2012, the European Parliament approved an agreement allowing the EU to exchange airline passenger information with the US.
In February, MEPs called on EU countries to make faster progress on a package of data protection reforms so that talks could continue alongside discussions of proposals on the communication of PNR.
According to The Register, "real movement" has been seen in the second round of 'trilogue' negotiations on the EU General Data Protection Regulation (GDPR) which covers companies' use of data.
Sources familiar with the discussions said that a "tentative political agreement has been reached on chapter 5 and Article 3 of the regulation", The Register said. These focus on territorial scope and international data transfers, it said.
The new text says that any company processing data about a European citizen within the European Union is subject to EU law, and any transfer of data outside the EU must meet certain standards, The Register said.
One point of disagreement was on exceptions to the rules for national security reasons, but The Register's source said that "an avenue is clear for agreement".
Discussions will continue in September, along with discussions on the Data Protection Directive which covers law enforcement agencies, The Register said.