Back in 2000, no-one could have predicted that those ousted from office in a popular uprising would overcome their Balkan pride to work with the very men they had come to hate.
Equally, no-one must be more surprised than supporters of the Socialist Party of Serbia (SP) over the choice - some would even say betrayal - their party leaders made when deciding to join the coalition led by the Democratic Party (DS) of President Boris Tadic.
Serbia's new coalition government - approved in parliament on Monday - represents the triumph of pragmatism over ideology and an apparent break with the past.
To many Serbs who have seen their country relegated to the back of the Balkan queue to join the European Union, the pledge of restarting their journey must be refreshing.
Delving into the past is a Balkan pastime - but many Serbs say they are now eager to look into the future.
Prime Minister Mirko Cvetkovic heads a disparate coalition of some 10 parties - at best an array of pragmatists with conflicting agendas.
The lowest common denominator has resulted in a programme for the next four years which has European integration at the top, followed by Kosovo - Serbia's southernmost province that declared independence with Western backing in February.
If Serbia is to move forward towards European Union membership, however, a large dose of pragmatism will be called for.
For, in addition to reforming the economy and fighting crime, Serbia's strange bedfellows may be asked to cross some red lines.
Kosovo is one.
Kosovo's independence declaration came at the end of a decade of wars in the territory of the former Yugoslavia, which were started in Kosovo by late SP leader, Slobodan Milosevic.
Mr Milosevic died in detention at the war crimes tribunal in The Hague in 2006 - but his party has yet to renounce him - or apologise for his policies that wrought catastrophic damage on Serbia.
Socialist voters are mostly Milosevic supporters, and the party leaders have taken a big gamble by turning their back on their more natural hardline allies - the Radicals and the party of former Prime Minister Vojislav Kostunica.
"There is a full consent among the coalition members that the new government will never recognise the independence of Kosovo," Mr Cvetkovic told MPs as he sought their support. A banner which says Kosovo is Serbia is prominently displayed on the Serbian government website.
But most of the 27 members of the bloc Mr Cvetkovic wants Serbia to join at the end of his mandate have recognised Kosovo's independence, and some indications suggest Serbia will be asked to do the same before the door is open.
Pragmatists may be able to do it - but using the word "never" may bring them into some difficulty with the electorate.
Kosovo has not been formally mentioned by the EU as a condition for Serbia's membership, but co-operation with the war crimes tribunal has, and it has been used to block Serbia's path in the past.
The government programme has only a lukewarm line about this.
The Hague's most-wanted men - former Bosnian Serb leader Radovan Karadzic and his wartime commander Ratko Mladic - are still at large, the latter believed to be in Serbia itself.
Belgrade has to arrest and deliver Mladic to The Hague, but the man now entrusted with hunting him down is none other than SP leader Ivica Dacic, the new interior minister.
This would be anathema to SP supporters.
So the EU might have to be more amenable to accommodate Serbia - or risk another election which no-one can conceivably look forward to.
Serbia's government wants both the EU and Kosovo - which appear to be mutually exclusive - and no substantive co-operation with The Hague tribunal into the bargain.
It may be an impossible circle to square. But everybody knows Serbia has made a seemingly clean break with the past and its leaders are ostensibly opposed to violence.