The Scottish National Party has broken Labour's eight-year dominance of the Scottish Parliament.
The SNP has emerged from the election with 47 seats, one more than its rival. The Tories ended up with 17, the Lib Dems with 16 and the Greens two.
Independent Margo MacDonald was returned to the new parliament.
Speculation is now rising about an SNP/Lib Dems/others coalition but a stumbling block could be the Nats' plans for an independence referendum.
A minimum of 65 MSPs will be needed to form a majority administration.
Scottish Liberal Democrat leader Nicol Stephen has regarded a referendum as a significant block to a power-sharing deal.
Under the Scotland Act, a new first minister has to be appointed within 28 days of the election, making the deadline 30 May.
The results came after a night of high drama, which saw the polls hit by major problems.
Seven counts were suspended amid claims that voters had been confused by the ballot papers and the decision to hold the local authority elections at the same time.
The Nationalists made significant gains, including SNP leader Alex Salmond winning in Gordon, and his deputy Nicola Sturgeon taking Glasgow Govan.
In an address aimed at setting out his credentials as a first minister in waiting, Mr Salmond said on Friday afternoon that the Labour Party had "lost the moral authority to govern Scotland".
"Scotland has changed for good and forever," he declared.
"There may well be Labour Governments and Labour first ministers in the decades to come but never again will we see the Labour Party assume that it has a divine right to rule Scotland.
"Labour has no moral authority left to govern Scotland."
Scottish Labour leader and current First Minister Jack McConnell pledged to "keep all options open" on how to go forward from the knife-edge outcome of the election, indicating he would not rush into any hasty coalition decisions.
The Holyrood poll will see 129 MSPs elected
He said: "I have not spent the last five-and-a-half years of my life as first minister building up Scotland and improving this country to make a snap decision this weekend about the future of our country, a decision that could affect every family across Scotland.
"Having fought an election campaign to put a strong economy, the foundation of our work - the education service - as our national priority, and action of crime and anti-social behaviour as fundamental, it is right and proper this weekend that I and my party reflect on how best to take forward these priorities in government and the parliament again."
Respondnig to Alex Salmond's comments claiming a moral authority, Mr McConnell added: "While I recognise that the SNP are the largest party by the narrowest of margins, Alex Salmond must himself recognise that he does not have a majority in the Scottish Parliament or anywhere near a majority of the vote.
"There is no moral authority to pursue separation and moral authority in the parliament will only come through different parties working together in the majority. Any attempt to suggest otherwise is, at this stage, highly premature."
Scottish Conservative leader Annabel Goldie said she was proud of her party's election campaign.
She said: "Proud that we have talked relentlessly about the issues - the bread and butter issues - which really matter to the people of Scotland.
"Defeating drugs, cutting crime, affordable homes, standing up for families and proud too that we have stood up and defended the Union."
Ms Goldie added: "I promise that over the next four years, the Scottish Conservatives will continue to be a voice for common sense at Holyrood and will never compromise on our ideals.
Scottish Lib Dem leader Mr Stephen, the current deputy first minister, said he was committed to delivering his party's key policies on energy, health and young people.
"Day after day, the Liberal Democrats have promoted a positive programme, focused on families and on children," Mr Stephen said.
"The Liberal Democrats, in this new Scottish Parliament, are determined to deliver on our key policies.
"My commitment is to these policies and to a bright future for Scotland."