By Dominic Hughes
Europe Reporter, BBC News
Mr Leterme has put together a five-party coalition
Yves Leterme of the Flemish Christian Democrats is the country's new prime minister, taking over from Guy Verhofstadt who stands down after nine years in office.
But the negotiations leading to the formation of this coalition government have been long and tortuous.
The key sticking point was constitutional reform.
Mr Leterme, a clear winner from the elections in June of last year, had promised his supporters real and significant change.
In Europe's most devolved state, he wants to pass yet more powers from Belgium's federal government to the regions.
Matter of money
But while there is strong backing for this in the Flemish Dutch-speaking north of the country, French-speakers in Wallonia in the south are unimpressed.
Their region is much poorer, with higher unemployment and a stuttering economy.
Some fear "constitutional reform" is a way of reducing the amount of money the wealthy Flemish transfer to impoverished Wallonia.
For their part, Flemish politicians argue that it is only fair they have a say in how some of that money is spent. Why should they subsidise failed economic policies and high unemployment in Wallonia, they ask.
So after the election came months of stalemate.
Constitutionally - and practically - an administration must include members of both language groups in this linguistically-divided country.
Deeply divided
But once again the gulf that exists between the Dutch and French speakers was exposed.
The two communities seem to exist side-by-side, but with little interaction.
There are no national political parties or newspapers, radio or TV stations.
Even the new prime minister has said it is only the king, a love of beers and the football team that unites Belgians - and the football team has not been that great in recent years.
Mr Leterme has also described Belgium as "an accident of history" with "no intrinsic value", and went on to describe French speakers as "lacking the mental capacity to learn Dutch". He is nothing if not plain speaking.
So in December last year, after more than 190 days of talks, King Albert II stepped in and called a halt.
He asked the defeated Mr Verhofstadt to head an interim administration for three months with authority to pass legislation and to start work on a national budget.
Deal struck
In fact Mr Verhofstadt had been acting as PM anyway while negotiations went on, but with very limited authority.
A bit of breathing space for the parties seemed to do the trick.
At 5am on Tuesday, bleary-eyed journalists heard Mr Leterme announce a deal had been done to stitch together a five-party coalition, including French-speaking socialists and his own centre- right Flemish Christian Democrats.
But the document that the deal is based on fails to address the main stumbling block of constitutional reform.
That has been farmed out to a committee of "wise men" who have to produce proposals by 15 July.
And if the Christian Democrats do not like what they see then, they have already warned they will walk out of the government.
So a fresh political time bomb is ticking under the new administration even as it takes office.
After almost nine and a half months, government formation talks in Belgium have resulted in a new government. New Prime Minister Yves Leterme was sworn in by King Albert II today, together with 15 new Ministers and 7 Secretaries of State. After the election on June 10 last year, a confidence vote in the parliament in Brussels on Saturday is expected to confirm the coalition's promise of a government in time before Easter.

In his inaugural speech, Flemish Christian Democrat Leterme replied to criticism from the media and opposition that his government's manifest was vague and that there was no mutual trust between the coalition partners: "We want to increase the faith in the government, not with empty promises, but with specific measures, by investing in health care, the environment, safety and governmental services."

The coalition partners have set out several deadlines for major decisions on which agreement still could not be reached during the formation. By July 15, a council of 'wise men' has to fill the current empty space of the promised constitutional reforms. Yesterday, a survey published in the media showed that the majority of Belgians lacked confidence in the new government, and believed it will collapse within months. On a party convention yesterday, Leterme pledged he would keep his promise to his constituency, vowing to break up the government if more powers are not devolved to the regions.

The record-breaking political stalemate had promised to be difficult from the start, after the Christian Democrats won the elections in Flanders in coalition with the nationalist party N-VA. The cartel promised more regional autonomy for the northern Dutch-speaking two-thirds majority of Belgium. Negotiations promised to be tough in a country where separate parties for the main ideologies exist in each half of the country.

Political map of Belgium showing Dutch-speaking Flanders (yellow), French-speaking Wallonia (red), German-speaking area (blue striped) and bilingual Brussels Capital Region (orange).
Leader of the separatist N-VA Bart De Wever expressed his disdain about the new government: "There are more Francophone than Dutch-speaking members in this administration, which doesn't respect the proportions: Flanders has two thirds of the population and three quarters of the wealth."

During the political crisis the previous PM Guy Verhofstadt, who recognised his defeat in the elections and had seemingly withdrawn from the political stage, returned to head a caretaker government at the request of the Belgian King. In his inaugural speech today, the new PM expressed his gratefulness to Verhofstadt for his services. After almost 9 years as the Belgian PM, Verhofstadt presented his successor with the keys of his new residence at ''Rue de la Loi 16''/''Wetstraat 16'' ("16 Law St."), in Brussels.

'Madame No' Joëlle Milquet, leader of the Walloon Christian Democrats, gave her Flemish colleague Leterme a hard time during the coalition talks because she consistently resisted the Flemish demands for regional autonomy. In the new government she becomes the federal Minister of Work, a department that the Flemish nationalists want to devolve to the regional level.

As the largest political fraction, the liberals seem to have weighed heavily on the coalition. They deliver the vice-Premier and the Ministers for Constitutional Reforms, Finances, Economy, Internal and Foreign Affairs, Asylum and Migration, Agriculture, Sciences and Humanitarian Aid. The French-speaking socialists joined the coalition talks late in the process, while the Flemish socialists remain in the opposition, giving an unprecedented asymmetry to the federal government.