"President Yeltsin was a historic figure who served his country during a period of momentous change," U.S. President George W. Bush said in a statement, shortly after learning of Yeltsin's death Monday from heart failure. "He played a key role as the Soviet Union dissolved, helped lay the foundations of freedom in Russia and became the first democratically elected leader in that country's history."
There was no immediate word on whom the U.S. government would send to attend Yeltsin's funeral, which the Kremlin said would be held on Wednesday.
"Although we would sometimes have massive divergences over our politics, we were both, nevertheless, trying to do what we thought best for our country and its people," Mikhail Gorbachev, whose reforms prepared the way for Yeltsin's political rise, wrote in a personal letter to Yeltsin's widow, Naina. He called Yeltsin's passing a "loss that cannot be replaced."
U.S. Secretary of State Condoleezza Rice, whose academic career was largely spent studying the Soviet Union, said Yeltsin "ushered in a new era for his country in which ordinary Russians were able to speak and worship without fear, to own property, and to choose their leaders freely.
"In doing so, he inspired a generation of young Russians to build a bright new future for their country and to choose peaceful relations with their new neighbors," she said in a statement.
Others hailed Yeltsin as a healer of the Cold War divide, opening up Russia to the rest of Europe.
Yeltsin "will be remembered for the critical role he played in advancing political and economic reforms in Russia, as well as in fostering rapprochement between East and West," U.N. Secretary-General Ban Ki-moon said, according to a spokeswoman.
Many leaders said Yeltsin would be best remembered as standing on a tank outside the Russian parliament building, defying the coup aimed at restoring a dictatorial regime in Russia. Others praised the difficult path he followed in acknowledging the independence of former states of the Soviet Union.
"It's largely thanks to Yeltsin that we got free without bloodshed," Estonian lawmaker Peeter Tulviste told the Baltic News Service.
Former British Prime Minister Margaret Thatcher said that without Yeltsin, "Russia would have remained in the grip of communism and the Baltic states would not be free. He deserves to be honored as a patriot and liberator."
Nobel Peace Prize laureate and former Polish President Lech Walesa said it was Yeltsin, not Gorbachov, who was the driving force that ultimately led to the dismantling of the Soviet Union.
"If he hadn't done that, all the processes across the world of that sort would have come to a halt and been drawn back, and so the great service of Yeltsin is what we have today - a free world, the era based on knowledge, the internet, globalization. And so we bow our heads in his memory," said Walesa.
Yeltsin's personality could be as strong as his actions, leaders remembered.
"He could be moody and introspective, but once he was a friend, he was a friend for life," former British Prime Minister John Major told the British Broadcasting Corp. "I think his tremendous work in terms of instilling democracy is what will stand out when people have forgotten the economic difficulties, and forgotten the miscellaneous matters about as whether he drank too much."
In August 1994, Yeltsin's antics as he and then-German Chancellor Helmut Kohl presided over an otherwise dignified withdrawal of the Red Army from east Germany endeared him to Germans. On the steps of Berlin's Rotes Rathaus city hall, a flush-faced Yeltsin grabbed a police band conductor's baton and began directing the musicians. German officials later told an AP reporter that Yeltsin had begun drinking before noon.
"Boris Yeltsin was a large personality in Russian and international politics, a courageous fighter for democracy and freedom and a true friend of Germany," current German Chancellor Angela Merkel said.
"Fate gave him a tough time in which to govern, but history will be kind to him because he was courageous and steadfast on the big issues - peace, freedom, and progress," former U.S. President Bill Clinton and Democratic presidential candidate Hillary Clinton said in a statement.
South African President Thabo Mbeki called Yeltsin "indeed a friend of South Africa in his endeavors to consolidate and strengthen political, cultural and people-to-people relations between the Russian Federation and South Africa." Yeltsin was president when the African National Congress finally came to power in 1994 elections after a fight against white minority rule.
Yeltsin's health was the source of more than one vivid memory Monday. Sweden's former Prime Minister Goran Persson described him as having "no coordination between movement and thought" during a December 1996 visit to Stockholm, shortly afterhaving heart surgery.
"It was a bit uncomfortable, actually," Persson said in comments first broadcast in a recent TV documentary. "This was not a person who lacked influence, and yet you could tell how incredibly tired he was."
Yeltsin's death startled Ukraine's first president, Leonid Kravchuk, who said he saw Yeltsin in January during a tennis tournament.
"He looked so healthy," Kravchuk said. "His death became a huge emotional shock for me."