However the deal - a watered-down version of an original 2001 proposal - was criticized by some for not going far enough to deter racism, xenophobia and anti-Semitism, which have been on the rise across Europe in recent years.
EU justice and interior minister reached the deal after six years of difficult and often tense negotiations. The new rules would set only minimum standards for fighting racism and xenophobia, and still must be vetted by national parliaments.
"It is going to have implications for member states legislation," said German Justice Minister Brigitte Zypries, who chaired the talks. "It is an important political signal for the EU."
EU Justice and Home Affairs Commissioner Franco Frattini said the new rules were aimed at sending a strong message of Europe's commitment to fighting racism, xenophobia and anti-Semitism.
With an eye to Europe's Nazi past, Frattini said the EU had "a moral authority to reaffirm ... values of tolerance, of refusal of any kind of violence."
"There are no safe havens in Europe for racist violence, for anti-Semitism, for people concretely inciting xenophobic hatred," he said.
The text of the agreed draft commits EU governments to imposing criminal sanctions against people or groups "publicly inciting to violence or hatred ... directed against a group of persons or a member of such a group defined by reference to race, color, religion, descent or national or ethnic origin."
It also calls for EU nations to impose up to three-year prison sentences for those convicted of denying genocide, such as the mass killing of Jews during World War II and the 1990s massacre in Rwanda. That rule would apply only to genocides that have officially been recognized under statues of the International Criminal Court.
Reaching the deal was difficult amid the 27 EU member countries, which have vastly different legal and cultural traditions in combatting racism. For example, EU nations including Germany, France, Spain, Austria and Belgium already ban denials of the Holocaust, but others such as Denmark allow the publishing of hate literature under their freedom of expression legislation.
Yad Vashem, Israel's Holocaust memorial authority, welcomed the agreement, but said EU governments should go further to teach their citizens about the past.
"We welcome the EU decision and believe that Holocaust denial legislation is an important tool in fighting Holocaust denial and hate. Legislation must be accompanied by educational activity," it said in a statement.
In the six-year effort to reach an agreement, the original draft was diluted with numerous opt-outs. The EU ministers also rejected a call from Baltic nations to include major Stalinist atrocities in the EU law.
Zypries said that the compromise was reached on the basis that the EU would organize a public debate on other massacres or hate crimes not included in the new rules, notably those committed during Soviet or Communist time.
Anti-racist groups and other critics slammed the final draft, however, saying it would do little to boost existing national anti-racism rules, many of which already go further than the agreed-to EU measures.
A statement this week from the European Network against Racism - a grouping of more than 600 nongovernmental organizations - called the draft text "weak" and objected that "many escape clauses have been introduced to allow member states to circumnavigate their responsibilities."
It said vague terms in the proposal and weak jail terms would do little to take a firm stand against anti-Semitism and other racist incitement.
Several countries, including Britain, Italy and Denmark, had been reluctant to sign up to the measures because they feared EU-wide laws could overstep the right to expression protected under their countries' laws.
More contentious aspects of the draft rules require member states to criminalize those "publicly condoning, denying or grossly trivializing ... crimes of genocide, crimes against humanity and war crimes," as defined under international law.
But EU nations can choose to opt out of such punishment if such rules do not exist under their national laws.
Opt-outs also are foreseen for racist remarks based on religious grounds and on Nazi symbols, such as the swastika.