The rules will for the first time create a strong data protection law for Europe's 500 million citizens, replacing an outdated patchwork of national rules that only allowed for tiny fines in cases of violation.
The rules also state that individuals must give their "clear and affirmative consent" before private data is processed by companies or governments. This point became important after leaks two years ago showed allegedly widespread US government snooping of European data such as phone calls and emails.
The new rules also allow for the streamlining of data transfers for policing and judicial purposes, helping to improve security in the wake of the November 13 attacks in Paris, which killed 130 people, and last month's suicide bombings in Brussels, which left 32 dead.
Privacy has become a hot topic amid pressure by companies to get information on consumers, as well as the needs of security services to have as much data as possible on possible suspects involved in extremist attacks.
The European parliament's president, Martin Schulz, said that "the security of European citizens should never be ensured at the expense of their rights and freedoms."
But he welcomed the new rules as "crucial steps" in the digital age when the privacy of consumers has come under ever greater threat.
Commercially, there also is a lot a stake and the parliament's chief negotiator, Jan Philipp Albrecht, has said that firms breaching EU data protection rules could be fined as much as 4 percent of annual turnover, which could amount to billions in dollars.
After four years of fierce political battles between industry and privacy groups, the rules should now become official within a two-year span.