His globe-trotting escape has compounded the crisis for Washington unleashed by his leaks about its global spying and hacking operations, and threatens to strain US relations with both Moscow and Beijing.
Snowden, the target of a US arrest warrant issued on Friday after the IT contractor leaked details of US cyber-espionage programmes to the media, arrived in Moscow on Sunday on a direct flight from Hong Kong and was expected to head to Ecuador via Cuba.
The US government called Hong Kong's decision to allow the former National Security Agency (NSA) contractor to travel "troubling", as the State Department had revoked his passport and ordered other countries to prevent him from travelling.
Snowden, aged 30, landed at Moscow's Sheremetyevo airport on a scheduled Aeroflot flight at 17:05 pm (1305 GMT) on Sunday, an AFP correspondent at the airport said.
He did not emerge into the main terminal area, where crowds of journalists quizzed his jet-lagged and bewildered fellow passengers about whether they had seen the Snowden on the flight.
Spending night in 'capsule hotel'
An airport source told Interfax that "transit passenger" Snowden had remained within the airport. "He would not be able to leave the airport even in a diplomatic car - he has neither a standard nor a diplomatic visa," the official said.
AFP correspondents earlier saw an Ecuadoran flagged diplomatic car at VIP arrivals. The Ecuadoran ambassador to Moscow was reportedly at the airport to meet Snowden.
Airport officials said Snowden was spending Sunday night in the Vozdushny Express "capsule hotel" inside the departures area ahead of his next flight.
Russian media reports cited sources within Aeroflot as saying he would fly onwards to Cuba on Monday. The SU 150 flight to Havana leaves at 1005 GMT.
Initial reports said the man behind one of the most significant security breaches in US history would fly to the Venezuelan capital Caracas, but Ecuador's foreign minister said Snowden had asked Quito for asylum.
The South American country, led by outspoken leftist President Rafael Correa, has been sheltering WikiLeaks founder Julian Assange, who is wanted by Sweden, at its London embassy for the past year.
'Assault against the people'
The WikiLeaks website said it had helped organise Snowden's safe exit and confirmed he "is bound for the Republic of Ecuador via a safe route for the purposes of asylum".
Russian officials said Snowden could still potentially make it to Ecuador without a valid US passport.
"If he has asked for asylum in Ecuador then they could give him a refugee document or even Ecuadorian citizenship allowing him to continue his journey," a security source told Interfax.
Former Spanish judge Baltasar Garzon, legal director of WikiLeaks, condemned the pursuit of both Assange and Snowden as an "assault against the people".
WikiLeaks confirmed that Snowden was accompanied by a British citizen named Sarah Harrison, whom it described as a "journalist and legal researcher" working with the WikiLeaks legal team.
Snowden's latest interview published on Sunday contained new revelations about US cyber-espionage against Chinese targets, drawing a stinging response from China's official news agency Xinhua, which branded Washington a spy "villain".
Terror plots foiled
In the revelations in Hong Kong's Sunday Morning Post, Snowden said the NSA was hacking Chinese mobile phone companies to gather data from millions of text messages.
He said US spies have also hacked the prestigious Tsinghua University in Beijing - home to one of six "network backbones" that route all of mainland China's Internet traffic - and the Hong Kong headquarters of Pacnet, which operates one of the Asia-Pacific region's largest fibre-optic networks.
Snowden abandoned his high-paying job in Hawaii and went to Hong Kong on 20 May to begin issuing a series of leaks on the NSA gathering of phone call logs and Internet data, triggering concern from governments around the world.
US President Barack Obama's administration, which on Friday unveiled charges including theft and espionage against Snowden, has insisted on the legality of the spy programmes and said they had helped foil around 50 terror plots.
Hong Kong, a special administrative region (SAR) under Chinese rule that has maintained its own British-derived legal system, said it had informed Washington of Snowden's exit after determining that the documents provided by the US government did not fully comply with Hong Kong legal requirements.
"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 said in a statement.
The US Justice Department insisted officials had fulfilled all the requirements of Washington's extradition treaty with Hong Kong.
"The US is disappointed and disagrees with the determination by Hong Kong authorities not to honour the US request for the arrest of the fugitive," it said in a statement.
"At no point, in all of our discussions through Friday, did the authorities in Hong Kong raise any issues regarding the sufficiency of the US's provisional arrest request."
In light of this Hong Kong's decision was "particularly troubling", the statement continued.