Social Democrat leader Stefan Löfven took the stage at the Waterfront Conference Centre in Stockholm at around midnight.
"I'll talk to other parties. My hand is outstretched. I'll talk to the Greens, but also to other parties," he said, making it clear he did not mean the Sweden Democrats.
"I want to thank Fredrik Reinfeldt, I have a lot of respect for you as a person and politician and I wish you all the luck," he added.
The anti-immigrant Sweden Democrats were by far the biggest winners of the night. They doubled their votes, to about 13 percent.
The group was a virtual non-entity less than a decade ago, and only entered parliament in the 2010 election, winning 5.7 percent of the vote and 20 seats in the 349-seat legislature.
Sunday's result is a major triumph for its leader, 35-year-old Jimmie Åkesson.
"We're the absolute kingmakers now," Åkesson said in front of his supporters in the Swedish capital.
Sweden Democrat leader Jimmie Åkesson. Photo: TT
He told broadcaster SVT that the other parties, which have refused to negotiate with the Sweden Democrats in parliament since 2010, "can't ignore us the way they have ignored us over the past four years."
"You have to be able to govern this country for four years, and it's going to be hard if they are not prepared to talk to us or listen to us," Åkesson told SVT.
Åkesson has carried out a lengthy campaign to clean up the party's image as a fringe phenomenon, expelling members whose xenophobic remarks have contributed to its racist reputation.
Sweden's outgoing Prime Minister Reinfeldt has been widely credited with steering the country through the global financial crisis, consolidating Sweden's position as one of the healthiest economies in Europe.
Despite these accomplishments, many Swedes yearned for fresh faces at the top and in Monday many commentators cited this as a main reason for the centre-right's changing electoral fortunes.
Meanwhile, the Sweden Democrat's huge advances are seen due to growing concern in Sweden over an accelerating influx of refugees, with up to 90,000 expected to travel to the Nordic country this year.
The Local asked Joakim Isheden, who is on the Board of Directors for the Sweden Democrats party's youth wing if he thought the result would change Sweden's global image.
"Yes but in a good way. We have a reputation for accepting more immigrants than anywhere else in Europe. I think this result will show other countries that it is time for them to change too. We just can't keep going in the same direction", he said.
The electoral gain for the Sweden Democrats confirms a Europe-wide trend of soaring popularity for populist right-wing parties.
The eurosceptic Alternative for Germany, which has flirted with populist positions on immigration and law and order, made gains in elections Sunday in the eastern states of Thuringia and Brandenburg.
The Feminist Initiative, which looked set to break through the 4 percent threshold during the exit polls, finished just above 3 percent and missed the chance of a spot in parliament.
A supporter of the Feminist Initiative. Photo: TT
Political scientist Nick Aylott told The Local that the evening's results were largely expected, but he added that the new government did not look like a particularly strong one.
The Social Democrats and the Greens can't go it alone, as much as they would like to, he explained.
"They may need at least two other parties to be sure of getting legislation through," Aylott said. "And that may be tricky."
He added that all of the current parliamentary parties seemed disappointed with their numbers - with one exception.
"The far-right Sweden Democrats appear to have more than doubled their score," Aylott remarked.
"The other parties will try desperately to continue the Sweden Democrats' isolation. But that will now be a real challenge, and will create acute dilemmas for several parties."
Green Party co-leader Gustav Fridolin shares a kiss with his wife. Photo: TT