The anti-Islam Alternative for Germany party won around 14 percent, according to public broadcasters' projections, in the capital which has long prided itself on being a hip, diverse and multicultural city.
The strong AfD result, thanks to support especially in the vast tower block districts in Berlin's former communist east, meant it has now won opposition seats in ten of Germany's 16 states, a year ahead of national elections.
Merkel's centre-right Christian Democratic Union (CDU) won only 17.5 percent - its worst post-war result in the city, before or after the 1989 fall of the Berlin Wall - likely spelling the end of its term as junior coalition partner to the Social Democrats (SPD), who won around 22 percent.
The election in the chronically indebted city-state of 3.5 million people was dominated by local issues including poor public services, crumbling school buildings, late trains and a housing shortage, as well as problems in coping with the migrant influx.
The biggest EU economy took in one million asylum seekers last year, and over 70,000 of them came to Berlin, with thousands still housed in the cavernous hangars of the Nazi-built former Tempelhof airport, once the hub for the Cold War-era Berlin airlift.
Berlin's SPD Mayor Michael Müller had dramatically warned before the polls that a strong AfD result would be "seen throughout the world as a sign of the resurgence of the right and of Nazis in Germany".
'Zero to double-digits'
The vote marked another milestone for the upstart AfD, which has campaigned on a xenophobic platform, similar to France's National Front or far-right populists in Austria and the Netherlands.
"From zero to double-digits, that's a first for Berlin," cheered the AfD's top Berlin candidate, Georg Pazderski, predicting that the electorate would next year kick out Merkel's national right-left grand coalition.
"We've arrived in the capital," said the party's co-leader Beatrix von Storch, hailing the "huge success".
Merkel's CDU, which has a national majority, in Berlin has served as junior coalition partner to Müller's SPD, traditionally the strongest party in the city .
Müller has rejected a new coalition with the CDU and was seen likely to team up with the ecologist Greens and the far-left Die Linke party, each of whom scored around 15 percent.
Such a "red-red-green" coalition, its members hope, could one day be replicated at the national level.
Merkel meanwhile - after suffering a stinging loss to the AfD in another regional poll two weeks ago - will face further pressure "to explain her political strategy", Gero Neugebauer of Berlin's Free University told the Handelsblatt business daily.
Another analyst, Kai Arzheimer of Mainz University, also predicted tensions would rise between the CDU and its Bavarian sister party the CSU, but he stressed the alliance was unlikely to change its top candidate, Merkel.
"To ask this question one year before federal elections would be suicidal, especially since in the CDU there is no credible successor," he said.
The CSU's Bavarian Finance Minister Markus Soeder nonetheless launched a broadside, charging that Merkel's government must "regain citizens' support in the refugee question and finally strictly limit immigration and get a handle on the security problems."
In Berlin - a city famously dubbed "poor but sexy" by its previous mayor, bon vivant Klaus Wowereit - the election campaign was dominated not just by migrant policies but also widespread frustration over poor public services.
With little industry and an above-national average jobless rate of 10 percent, Europe's techno party capital is often seen as an amusingly chaotic exception in otherwise orderly and punctual Germany.
Berlin became a national laughing stock for a grand airport project that is now five years behind schedule and three times over budget.