Demjanjuk, 89, appeared to be crying as was carried from his house on a stretcher and driven away in a private ambulance past a small crowd which had gathered nearby.
He was boarded onto what sources said was a Munich-bound air ambulance flight which departed as the sun was setting over Cleveland's Burke Lakefront Airport at 7:13 pm (2313 GMT.)
Four agents took part in removing Demjanjuk from his home in an operation which was screened from public view by a large sheet.
His family said they would not be making any further statements Monday and US officials also declined to comment.
A German official said Demjanjuk was expected in Germany on Tuesday.
"We assume from what we know at the moment, that he will probably arrive in Germany tomorrow," justice ministry spokesman Ulrich Staubigl told AFP Monday morning.
Two priests were seen visiting Demjanjuk's home early Monday and several members of his family also came to say goodbye.
The deportation marked the end of months of legal wrangling and closes a chapter on a decades-long saga over Demjanjuk's war-time activities.
Arguing that the octogenarian is too ill to travel, his family sought to stay his deportation through a succession of appeals, culminating last week in a failed bid to the US Supreme Court.
His son expressed the family's frustration and disappointment in an e-mailed statement.
"Given the history of this case and not a shred of evidence that he ever hurt one person let alone murdered anyone anywhere, this is inhuman even if the courts have said it is lawful," John Demjanjuk Jr wrote Monday. "This is not justice, it is a vendetta in the falsified name of justice with the hope that somehow Germany will atone for its past."
A prominent Jewish organization welcomed the news.
"The long arm of American justice has successfully and righteously executed judgment against this heinous Nazi persecutor," World Jewish Congress president Ronald Lauder said in a statement. "The American Jewish community, and particularly those who survived the Holocaust, welcome the removal of this vile individual from our midst."
Equally jubilant was the Simon Wiesenthal Center, which noted that the prosecution of Demjanjuk "will probably be the last trial of a Nazi war criminal," said the group's founder Rabbi Marvin Hier. "His defenders say that at 89, he is too old to be deported. His 29,000 victims would have only wished that they would have been so fortunate to reach the age of 89," said Hier, whose group is devoted to fighting anti-Semitism around the world.
Born in Ukraine in 1920, Demjanjuk was a soldier in the Red Army when he was captured by the Nazis in the spring of 1942.
He was trained at Treblinka in Nazi-occupied Poland and served two years in the Sobibor and Majdanek camps, also in occupied Poland, and in Flossenburg in Bavaria, southern Germany, court filings showed.
Demjanjuk has always insisted that he was forced to work for the Nazis and had been mistaken by survivors for other cruel guards.
He immigrated to the United States in 1952 with his family, settling in Ohio, where he found work in the auto industry and changed his name from Ivan to John.
Condemned to death in Israel in 1988 after he was convicted of being the sadistic Nazi guard nicknamed "Ivan the Terrible," the verdict was overturned by the Israeli Supreme Court because of doubts about his identity.
He was returned to the United States over strenuous objections from Holocaust survivors and Jewish groups, who argued there was sufficient evidence that he served as a death camp guard to warrant another trial.
Demjanjuk regained his US citizenship, which was first stripped in 1981, after an appeals court ruled in 1998 that the US government recklessly withheld exculpatory evidence.
The US government filed new charges a year later using fresh evidence that surfaced following the collapse of the Soviet Union, and he was again stripped of his US citizenship in 2002.
Germany issued a warrant for Demjanjuk's arrest on March 11 on charges of assisting in the murder of 29,000 Jews at Sobibor.