Moscow, and the anti-secrecy group WikiLeaks said in a statement he was "bound for the Republic of Ecuador via a safe route for the purposes of asylum".
Ecuadorean foreign minister Ricardo Patino, visiting Vietnam, tweeted: "The Government of Ecuador has received an asylum request from Edward J. #Snowden."
Ecuador is sheltering WikiLeaks' founder Julian Assange at its London embassy, and Ecuador's ambassador to Russia said he expected to meet Snowden in Moscow on Sunday.
Ecuadorean president Rafael Correa has good ties with WikiLeaks and is in a politically confident mood after his recent landslide re-election.
Snowden's departure from Hong Kong, a former British colony that returned to China in 1997, is likely to be highly embarrassing for the administration of president Barack Obama.
U.S. authorities had said only on Saturday they were optimistic Hong Kong would cooperate over Snowden, who revealed extensive U.S. government surveillance in the United States and abroad.
Earlier, a source at the Russian airline Aeroflot had said Snowden would fly on from Moscow within 24 hours to Cuba, although the source said he planned to go on to Venezuela.
Venezuela, Cuba and Ecuador are all members of the ALBA bloc, an alliance of leftist governments in Latin America that pride themselves on their "anti-imperialist" credentials.
Ecuadorean Ambassador Patricio Alberto Chavez Zavala told reporters at a Moscow airport hotel that he would hold talks with Snowden and Sarah Harrison, a WikiLeaks representative.
"We're waiting for Sarah. We're going to talk to them," he said, without revealing what the discussion would cover.
Surveillance activities leaked
Snowden, who worked for the National Security Agency, had been hiding in Hong Kong since leaking details about the U.S. surveillance activities to news media.
In their statement announcing Snowden's departure, the Hong Kong authorities said they were seeking clarification from Washington about reports of U.S. spying on government computers in the territory.
The Obama administration has previously painted the United States as a victim of Chinese government computer hacking.
This month Obama called on his Chinese counterpart Xi Jinping to acknowledge the threat posed by "cyber-enabled espionage" against the United States and to investigate the problem when they met in California. Obama also met Russian President Vladimir Putin in Northern Ireland last week.
A spokesman for the Hong Kong government said it had allowed the departure of Snowden - regarded by his supporters as a whistleblower and by his critics as a criminal and perhaps even a traitor - because the U.S. request to have him arrested did not comply with the law.
In Washington, a Justice Department official said it would seek cooperation with countries Snowden may try to go to.
Sources familiar with the decision said Washington had revoked Snowden's U.S. passport.
"It's a shocker," said Simon Young, a law professor with Hong Kong University. "I thought he was going to stay and fight it out. The U.S. government will be irate."
Obama agenda sidelined
Obama has found his domestic and international policy agenda sidelined as he has scrambled to deflect accusations that the surveillance violates privacy protections and civil rights.
The president has maintained that the measures have been necessary to thwart attacks on the United States, and the U.S. government filed espionage charges against Snowden on Friday.
WikiLeaks said Snowden was accompanied by diplomats and that Harrison, a legal researcher working for WikiLeaks, was "accompanying Mr Snowden in his passage to safety".
"The WikiLeaks legal team and I are interested in preserving Mr Snowden's rights and protecting him as a person," former Spanish judge Baltasar Garzon, legal director of WikiLeaks and lawyer for Assange, said in a statement.
"What is being done to Mr Snowden and to Mr Julian Assange - for making or facilitating disclosures in the public interest - is an assault against the people."
Assange has found sanctuary in the Ecuadorean embassy in London and said last week he would not leave even if Sweden stopped pursuing sexual assault claims against him because he feared arrest on the orders of the United States.
U.S. authorities have charged Snowden with theft of U.S. government property, unauthorised communication of national defence information and wilful communication of classified communications intelligence to an unauthorised person, with the latter two charges falling under the U.S. Espionage Act.
The United States had asked Hong Kong, a special administrative region (SAR) of China, to send Snowden home.
"The U.S. government earlier on made a request to the HKSAR government for the issue of a provisional warrant of arrest against Mr Snowden," the Hong Kong government said in a statement.
"Since the documents provided by the U.S. government did not fully comply with the legal requirements under Hong Kong law, the HKSAR government has requested the U.S. government to provide additional information ... As the HKSAR government has yet to have sufficient information to process the request for provisional warrant of arrest, there is no legal basis to restrict Mr Snowden from leaving Hong Kong."
It did not say what further information it needed. The White House had no comment.
China says US "biggest villian"
Although Hong Kong has an independent legal system and its own extradition laws, China controls its foreign affairs.
Some observers see Beijing's hand in Snowden's sudden departure. Iceland refused on Friday to say whether it would grant asylum to Snowden, a former employee of contractor Booz Allen Hamilton who worked at an NSA facility in Hawaii.
Putin's spokesman, Dmitry Peskov, said this month that Russia would consider granting Snowden asylum if he were to ask for it and pro-Kremlin lawmakers supported the idea, but there has been no indication he has done so.
The South China Morning Post earlier quoted Snowden offering new details about the United States' surveillance activities, including accusations of U.S. hacking of Chinese mobile telephone companies and targeting China's Tsinghua University.
Documents previously leaked by Snowden revealed that the NSA has access to vast amounts of internet data such as emails, chat rooms and video from large companies, including Facebook and Google, under a government programme known as Prism.
China's Xinhua news agency, referring to Snowden's accusations about the hacking of Chinese targets, said they were "clearly troubling signs".
It added: "They demonstrate that the United States, which has long been trying to play innocent as a victim of cyber attacks, has turned out to be the biggest villain in our age."