Yeltsin, 76, Russia's first ever democratically elected leader (1991-1999), died Monday afternoon at a Moscow hospital as a result of a heart failure.
U.N. Secretary-General Ban Ki-moon said 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."
President George W. Bush said Yeltsin was a "historic figure who served his country during a period of momentous change."
"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," the U.S. president said. "We offer our sincerest condolences to the Yeltsin family and to the Russian people."
British Prime Minister Tony Blair also expressed sadness at Yeltsin's death.
"He was a remarkable man who saw the need for democratic and economic reform and in defending it played a vital role at a crucial time in Russia's history," Blair said.
German Chancellor Angela Merkel described Yeltsin as a "courageous fighter for democracy."
"Boris Yeltsin was a great personality in both Russian and international politics, a courageous fighter for democracy and freedom and a true friend of Germany," Merkel said. "His contribution to the development of our relations between our two nations will never be forgotten."
French President Jacques Chirac said Yeltsin was a personal friend who strived to develop relations between France and Russia "in the spirit of dialogue and trust."
"Yeltsin put all of his energy, all of his generosity, all his desire into the transformation of Russia in order to construct a modern, democratic state and re-establish human rights and freedom and rebuild the economy," Chirac wrote in a letter addressed to Russian President Vladimir Putin.
The European Union and the NATO alliance praised Yeltsin as a leader who helped breach the Cold War divide by opening up Russia to the rest of Europe.
Javier Solana, the foreign policy and security chief of the European Union, called Yeltsin a key political figure of the 20th century.
"We have lost a very important figure in modern politics," Solana said. "Boris Yeltsin is a man we will never forget, who personifies a key political figure of the 20th century."
"Mr. Yeltsin was a key reference in the post-Communist transition in Russia. As president he had enormous challenges and difficult mandates but he certainly brought East and West closer together and helped replace confrontation by co-operation," President of the European Commission Jose Manuel Barroso said.
NATO Secretary General Jaap de Hoop Scheffer also praised Yeltsin's political courage.
"President Yeltsin will be remembered for his courage in charting a new, democratic course for his country," De Hoop Scheffer said in his statement. "He was also at the forefront of the effort to overcome the legacy of the Cold War by forging a new relationship between Russia and the North Atlantic alliance."
Japan's Foreign Ministry issued a statement Tuesday with condolences on behalf of the government and the Japanese people.
"Yeltsin made enormous efforts at promoting reforms in modern Russia and laid a new foundation for advancing Japan-Russia relations including efforts at resolving a territorial issue," the statement said in an apparent reference to the dispute over the Kuril Islands.
Russian President Vladimir Putin moved his annual state of the nation address to the upper house of the Russian parliament to Thursday, April 26, and declared Wednesday, April 25, a National Day of Mourning in observance of the passing of Boris Yeltsin, the Kremlin press service said Tuesday.
