"Germany and Israel are, and will always remain, linked in a special way through the memory of the Holocaust," said Merkel, who on Monday laid a wreath at Jerusalem's Yad Vashem memorial to victims of the Nazi genocide.
"The Holocaust fills us Germans with shame," said Merkel, the first German chancellor born after World War II. "I bow before the victims, I bow before the survivors, and before all those who helped them so they could survive."
Merkel said the 60th anniversary which Israel officially marks in May "is most of all an occasion for great joy."
She touched briefly on the decades-old conflict between Israel and the Palestinians.
"I say clearly and unequivocally: the Qassam (rocket) attacks by Hamas must stop," she said in reference to attacks on southern Israel by militants in the Gaza Strip, a Palestinian enclave run by theIslamist Hamas movement.
She stressed Berlin would not impose "unsolicited advice" on its ally on how to solve its decades-long conflict with the Palestinians.
"A solution can eventually only come about through you here in Israel, and with the Palestinians."
The German visitor drew loud applause when she opened her address in Hebrew, saying: "I thank you for the honour of allowing me to address the Knesset."
But the fact she delivered the rest of her speech in German ruffled feathers among MPs in a country where the memory of the Nazi murder of six million Jews still runs deep. Several lawmakers stayed away from the chamber in protest.
"I know the last sounds heard by my grandparents and my uncles ... were those of the German language," Arieh Eldad, an MP of the far-right National Union-National Religious Party said earlier in the day.
Addressing the controversy, Merkel explicitely thanked the deputies for allowing her to speak in German.
In her speech, she expressed concern over repeated calls by Iranian President Mahmoud Ahmadinejad for Israel to be wiped off the map. She insisted the onus was on the Islamic republic to prove that its controversial nuclear programme was not aimed at developing an atomic weapon.
Israel, widely considered the sole if undeclared nuclear power in the Middle East, suspects Iran of trying to develop atomic weapons through its
nuclear programme, a charge Tehran vehemently denies.
Israeli Prime Minister Ehud Olmert hailed Merkel's positions on Iran and said she had told him "any threat to Israel's security is a threat to Germany's security."
Opposition leader Benjamin Netanyahu, for his part, told Knesset members "Iran must know there is also a military option."
Merkel's three-day visit was designed to reiterate support of Israel by its most important political and trading partner in Europe.
On Monday, Hamas, which is pledged to Israel's destruction, slammed the German leader for ignoring the "holocaust" perpetrated by Israel in the impoverished territory.
Merkel's statements "reflect a moral degradation into which this chancellor has failed by supporting without failure an entity that commits massacres against Palestinian children, women and the elderly," Hamas said in a statement.
Earlier this month, an Israeli army blitz on Gaza, launched in response to rocket fire, killed more than 130 Palestinians, including several dozen children and other civilians. Five Israelis were also killed.