The decision -- taken by ministers over Greek objections -- is the culmination of weeks of pressure on Greece, the main gateway for the million refugees and migrants who entered Europe last year, stoking the continent's biggest such crisis since World War II.
Austria's foreign minister Sebastian Kurz then warned Macedonia that it should be ready to close its border to migrants, saying that Vienna may also begin turning refugees away in coming months as it struggles to cope with the surge from Greece through the Balkans.
A report adopted 10 days earlier by the European Commission, the EU executive, found Greece was failing to properly register and fingerprint migrants during inspections at the Turkish land border and several islands in the Aegean Sea last November.
"It is of utmost importance that Greece addresses the issues identified in the report adopted by the Commission as a matter of priority and urgency," EU ministers said in a document containing 50 recommendations published on the European Council website.
The document gave Greece, which is already struggling to emerge from a massive debt crisis, one month to "establish an action plan to remedy the deficiencies."
After a further two months, Greece must report back on how the scheme is being implemented.
If Greece fails to remedy the problems by mid-May, Brussels could authorise other member states to exceptionally extend border controls within the EU's cherished Schengen area, including with Greece, for up to two years, instead of the normal six months.
Such a scenario is outlined under article 26 of the Schengen border code.
Germany, which along with other member states introduced such border controls late last year, on Thursday extended the measures until May, the limit under current Schengen provisions.
The Schengen area allows passport-free travel through 26 countries, most of them in the EU, and is put forward as one of the major European achievements on unity.
Greece's 'substantial' costs
An EU source told AFP that Greece voted against the ultimatum, while Cyprus and Bulgaria abstained.
In a document published on the European Council website, Greece rejected the report's contention that it was responsible for "serious deficiencies" in border control and denied it was "seriously neglecting its obligations."
Greece also said it had taken a number of measures at "substantial national financial and social cost" and reminded Brussels that the massive influx on its borders would put any member state under "severe pressure."
However, it said it would continue cooperating with the EU and its institutions in dealing with the crisis.
The council website said Greece had to take action on registration procedures, sea border surveillance, border checks, risk analyses, human resources and training as well as equipment and international cooperation.
Germany, which received 1.1 million asylum seekers last year, has been the main destination for most of the migrants entering Europe.
German Chancellor Angela Merkel's liberal refugee policy came under fire again as French Prime Minister Manuel Valls warned it is not sustainable in the long run, even if it is "justified temporarily."
But Merkel, without naming the EU members involved, told reporters in Berlin there was "a group of countries" which may voluntarily accept more refugees in exchange for redoubled efforts from Turkey to tackle illegal immigration into, and out of, its territory.
She said this group, which will meet on the margins of an EU summit in Brussels on February 18-19, could also help Turkey financially.
Brussels and Ankara remain at odds despite their November aid-for-cooperation deal to curb the tide of migrants making their way from Turkey, which hosts 2.7 million mostly Syrian refugees.
A senior Turkish official said Friday that some 100,000 Syrian refugees are being looked after in camps inside Syria close to the Turkish border as they flee the latest upsurge in fighting.
As Ankara came under EU and UN pressure to open its border, Turkish President Recep Tayyip Erdogan on Thursday threatened to send the millions of refugees in Turkey to EU member states.
In an interview with AFP in Damascus, Syrian President Bashar al-Assad urged Europe to stop "giving cover to terrorists in the beginning and through sanctions imposed on Syria" and help Syrians return home.