The ruling coalition in Malaysia has suffered its worst election result in decades by winning only a simple majority, say election officials.
Prime Minister Badawi will now ask permission to form a government
Prime Minister Abdullah Ahmad Badawi's National Front coalition lost its two thirds parliamentary majority and control of five state assemblies.
Analysts blame ethnic tensions, crime, and inflation for a drop in popularity.
Opposition figure Anwar Ibrahim hailed the result as a message that it was time for change in Malaysia.
The ruling coalition won 137 out of 219 seats, with three results still to come in, the Election Commission said.
Mr Ibrahim's Justice Party has 31 seats out of the opposition's 82 so far, according to the commission's website.
Mr Badawi, in office since 2003, said he would meet the constitutional monarch on Monday and ask to form a new government. He dismissed suggestions that he would now face pressure from party members to step down.
His son-in law, Khairy Jamaluddin, told reporters: "We suffered a lot of losses tonight. But we are going to fight on. We are not going to quit. It is not the end of the world and we are going to get through this."
'Time for change'
The BBC's Robin Brant says no one expected the opposition to do so well across the board.
It is clear, he adds, that people wanted change and Chinese and Indian ethnic minority voters deserted the National Front, in power for 50 years.
Before the elections only one state was under opposition control, Kelantan.
The Election Commission confirmed opposition wins in Kelantan as well as Selangor, Perak, Kedah and Penang.
Former Deputy Prime Minister Anwar Ibrahim, who leads the opposition Justice Party, said the people of Malaysia had spoken.
"Today at the ballot box, you listened to your heart with a lot of conviction that the time for change has arrived..." he said.
"This is a defining moment, unprecedented in our nation's history. Today a new chapter has opened."
Mr Ibrahim has accused the government of widespread vote-rigging.
Voters are concerned about price rises and ethnic tensions
Our correspondent says there are many people who have as many suspicions about Mr Ibrahim as about the National Front's leaders. But, he adds, the claim that Malaysia has free and fair elections is not a just one.
Ethnic minorities make up more than a third of the population. Many complain that government policy has denied them fair access to jobs, education, and housing.
Growing tensions between minority communities and the Malay majority have dominated the election campaign and the government has appealed for calm.
The last time the National Front suffered a big setback, in 1969, it resulted in race riots, dozens of deaths and a state of emergency.
Our correspondent says there is not any sign of that sort of violence being repeated, but there is a fear of tension and anger and the next couple of days could be crucial.
Some violence linked to the election was reported in the east of the country on Saturday.
Police in Terennganu State said they had fired tear gas to disperse a crowd of several hundred people protesting at what they saw as vote-rigging.
Supporters of the opposition PAS stopped buses they suspected of carrying National Front coalition supporters pretending to be voters from the district, said local police chief Ayob Yaacob.
He said that 22 people had been arrested and the rest of the crowd ran away.
Today's voting was my first time ever. I have always wanted to vote for a more Islamic government that secures right of citizens to strengthen the family institution and to be safeguarded from corruption, nepotism and a single-ethnic monopoly in both the civil service and small industries. Politics in Malaysia is broadly determined by group-survival sentiments as my Muslim Malay and non-Muslim non-Malay friends have great reservation about giving their votes to opposition party of the other race/religion
Muhammad, Shah Alam, Selangor
To believe that racial harmony is possible in a country that has one set of rules for the majority and a different set for the minority is ridiculous. Why should I vote for a government that treats me not as a citizen of equal right but as a guest who simply enjoys the goodwill of his hosts?
Hari, Kuala Lumpur, Malaysia
I am currently a mature law student at a university in the United Kingdom. Having lived in a Malaysia since a child I do not believe that the Malaysian people, including the Muslims on the whole are just focused on Islamic issues. Everyday working class people are more interested in petrol prices, national budget and the economy. As for the issues pertaining to ethnic Indian minorities, I believe change can only happen for the better if the current Indian representative for the National Front is replaced.
Ashwin Kumar, Sheffield, United Kingdom
I'm on holiday in Malaysia at the moment. I'm from the UK. I've been walking around town today and I've never before seen so much hype about politics. There are banners everywhere. Haven't experienced the separate queuing system for women yet. But whenever my girlfriend and I are shopping the locals always talk to me and don't even acknowledge my girlfriend. Apart from that the people are nice but perhaps a little serious. I wish this country well.
Alex Morse, Kota Bahru Malaysia