Mr Swinney was the closest challenger

The election was called in the wake of the Donald Dewar's death from a brain haemorrhage, and under the legislation which created the Scottish Parliament, MSPs were bound to choose a new first minister within 28 days.

Afterwards Mr McLeish told MSPs: "It is a day with, from my point of view, a sense of excitement, a sense of exhilaration.

"I feel emotion, and a deep sense of humility."

He also accepted a "deep sense of challenge" from the comments by the other party leaders.

"I want to provide a leadership that will unite the parliament," he said.

Mr McLeish paid tribute to the leader of the Scottish Liberal Democrats, Jim Wallace, who had served as acting first minister.

Mr Wallace paid tribute to Mr McLeish

He said: "There can be no prouder moment in anyone's life than when they are asked to lead a great party which I love."

He also spoke of the challenge of leading a country which he loved.

"It is a very great privilege. Thanks for the honour - I won't let you down."

After the result was announced by the presiding officer, each of Mr McLeish's opponents congratulated him on his victory.

Mr Swinney said: "I wish Mr McLeish well in his office as First Minister.

"He will understand that I will fight harder for my party - a party I love very much.

Mr McLetchie challeneged for the Tories

"He said life as first minister in his brief term of office had been tough.

"I do not intend to make it any less tough for him and hopefully a great deal tougher in years to come."

Mr McLetchie said: "I would like to offer Henry McLeish congratulations on behalf of the Scottish Conservatives.

"We will certainly cross swords in the next two and a half years and there will be cross words.

"But that does not detract from the respect we have for the high office he holds and we acknowledge the demands and responsibilities he will have."

Jim Wallace said: "It will be a daunting challenge to follow in the footsteps of Donald Dewar. Let us remember that Henry McLeish was one of the craftsmen of this Parliament."

Mr Canavan secured three votes

Falkirk West MSP Dennis Canavan also offered his congratulations.

"Can I say first that my decision to stand against him does not indicate any ill will towards him.

"I've known Henry for many years, even before he was elected as an MSP, and I know that he has done good work for the people of Fife and for the people of Scotland in general.

"If I had still been a member of the Labour Party I might even have ended up voting for him. I hope that's not the kiss of death for his career."

Mr McLeish is expected to move quickly to announce a cabinet shake-up and changes behind the scenes, with the reorganisation of special advisers.