The Bundesrat, which represent the country's 16 states, voted down a proposal to raise minimum social benefits in the first such setback for Merkel since losing her majority in the upper house last May.
Just one state shy of passing the legislation, the chancellor's coalition of conservative Christian Democrats (CDU) and pro-business Free Democrats (FDP) was stymied by Saarland's decision to abstain from the vote.
Politicians said they planned to create a working group on the same day to find a compromise based on Labour Minister Ursula von der Leyen's proposal that have already been adopted by the lower house, the Bundestag, last month.
The changes would raise basic welfare benefit rates by €5 to €365 per month and create “non-cash” benefits, such as a chip card that gives needy children access to educational and recreational services.
During the Bundesrat debate, von der Leyen defended the reforms, saying the standard rate increase had been calculated with “all necessary transparency.”
The government had focussed on hard realities and followed the demands of the Constitutional Court “point by point,” she said.
The country's high court recently ruled that the terminology and payment system for welfare benefits was too confusing and must be changed by the end of the year. The current basic payment is €359 per month, but critics say this should be increased to at least €420.
Von der Leyen also argued that Germany's current economic recovery meant greater chances of finding employment for welfare recipients, saying Hartz IV should not become a “permanent condition.”
But Rhineland-Palatinate state premier Kurt Beck, a member of the opposition centre-left Social Democrats, sharply criticised the von der Leyen's proposal.
“Such a mess has never before been presented,” he said ahead of the debate.
Manuela Schwesig, a spokeswoman for the SPD, said she expected the legislative mediation committee talks to be "difficult and tense."
Merkel lost her Bundesrat majority in May, when her CDU was defeated in an election in Germany's most populous state, North Rhine-Westphalia.
The government has estimated there are around 6.5 million recipients of Hartz IV, including 1.7 million children, the long-term unemployed, the handicapped and those too sick to work.
Hartz IV was named after Peter Hartz, the head of a commission that suggested changes to Germany's labour market and welfare system in 2002. It specifically refers to long-term unemployment benefits instituted in 2005, and has become synonymous with former Chancellor Gerhard Schröder's highly unpopular Agenda 2010 reforms.