The former oil tycoon was quitely escorted out of his prison in northwestern Russia in a low-key operation, depriving journalists of any image of the former convict leaving his remote penal colony.
In a dizzying succession of events, several hours later Khodorkovsky flew to Germany, the prison service said, with the RAPSI legal news agency saying he was on his way to Berlin.
"After his release he flew to Germany where his mother is undergoing treatment," the prison service said in a statement, saying he had requested permission to travel abroad.
Putin pardoned Khodorkovsky, once Russia's richest man, a day after stunning the country last day by saying he asked for clemency on humanitarian grounds as his mother was ill.
More From This Section
"Guided by humanitarian principles, I decree that Mikhail Borisovich Khodorkovsky... Should be pardoned and freed from any further punishment in the form of imprisonment," said the decree signed by Putin today.
Less than three hours after the publication of the decree, his lawyers confirmed that Khodorkovsky, 50, had left his prison colony in the town of Segezha in the Karelia region.
By accident or design, the release has coincided with a major amnesty for prisoners convicted of non-violent crimes that is expected to see the Pussy Riot punk rockers freed in the next days.
Thirty foreign and Russian Greenpeace activists, arrested on hooliganism charges after their protest against Arctic oil drilling are also expected to escape prosecution.
"It's an unprecedented case in the history of modern Russia," said political analyst Valeria Kasamara. "It was not worked out what to say and how -- that is why they are hiding him."