Scottish Justice Secretary Kenny MacAskill announced his release on compassionate grounds in a press conference.
Megrahi, who has terminal prostate cancer, could be on his way home within hours to spend his dying days with his family.
Sources at a military airport near Tripoli, Libya, said that the plane which will take him back home was en-route to Glasgow Airport earlier today, suggesting he could leave this afternoon.
Megrahi, 57, was convicted of killing 270 people in the 1988 bombing of Pan Am flight. Some 189 Americans were among those who died in the airliner explosion.
The decision to free him is likely to cause outrage in the United States, where Secretary of State Hillary Clinton said she hoped he would stay behind bars.
A White House spokesman said the Obama administration "deeply regrets" the decision.
Mr MacAskill made the announcement at the Scottish Government's ministerial headquarters in Edinburgh.
He had been considering two applications – one for Megrahi to be moved from Greenock prison to Libya under a prisoner transfer agreement, and a separate application for him to be released early on compassionate grounds.
He rejected the first application, and opted for the latter course, meaning Megrahi is able to return home a free man.
In the build-up to his decision, Mr MacAskill came under intense US pressure to keep Megrahi behind bars.
On Wednesday a cancer specialist called for an "urgent" decision on Megrahi's future.
Professor Karol Sikora, who visited him in prison, said the Libyan had an "aggressive" form of prostate cancer which was no longer responding to treatment.
"We believe he has only a very short period of time to live," said Prof Sikora, who assessed Megrahi last month.
But Mrs Clinton said it was "absolutely wrong" to release Megrahi, and American relatives have been fiercely critical of the reported plans.
Speaking on Wednesday, before his release, she said: "We are still encouraging the Scottish authorities not to do so and we hope that they will not."
Megrahi successfully dropped his appeal against conviction on Tuesday.
The Times reported that Megrahi would be flown back to Libya on Colonel Muammar Gaddafi's private jet.
Tripoli-based Afriqiyah Airways, which runs Colonel Gaddafi's personal Airbus A340, contacted Glasgow airport yesterday to report that it would be collecting "a special passenger", the newspaper claimed.
However, the flight was cancelled during protracted negotiations over his fate.
Another plane is reported to have left a military base near Tripoli for Glasgow, carrying Libyan journalists.
Megrahi's wife Aisha told The Times she was "very happy" at the prospect of her husband returning to his homeland.
It was also reported that the convicted bomber had called his mother in Libya and told her he hoped to be with her by Ramadan,
Hajja Fatma, 95, told the Tripoli Post in Libya: "I do not close the house's door at all. I am expecting him to enter at any moment.
"Eleven years I did not spend the holy month of Ramadan with him, I am waiting for that day when he comes back."
She maintained that her son was innocent of killing 270 people in the Lockerbie bomb, saying "he would not slaughter a chicken".
Memorial of , at Dryfesdale Cemetery 
, the only individual convicted in connection with the bombing of  in 1988, has been released by Scottish  , on compassionate grounds.

Megrahi is suffering from   and will be allowed to return to his home country of Libya.

270 people were killed when, on December 21, 1988, the  flight from London's Heathrow Airport to New York's  was destroyed by a bomb whilst in flight over southern Scotland.

A police convoy escorted Megrahi from his former prison home in  to , where he boarded an  flight to . He was told he could not remain in Scotland on security grounds.

In announcing the release on compassionate grounds, Justice Secretary MacAskill stated, "Al-Megrahi now faces a sentence imposed by a higher power. It is one that no court in any jurisdiction could revoke or overrule. It is terminal, final and irrevocable. He is going to die".

The conviction remains controversial. Last year then-president of US group ''Victims of Pan Am Flight 103'' told ''Wikinews'' that the vast majority were satisfied in Megrahi's guilt. ''UK Families Flight 103'' painted a very different picture to ''Wikinews'' of the opinions in Britain: "UK Families have different views about Megrahi's guilt or innocence.  Certainly some, including my husband and I, believe that we are not in a position to make a judgment about whether he was involved in some way or not," said group coordinator Jean Berkley, whose son was killed. "Much of the evidence at the trial was circumstantial and confusing and it is a fact that the Scottish Criminal Cases Review Commission, after considering the matter for three years, came to the conclusion that there were grounds for appeal. The UK families are united in believing that the full independent inquiry for which we have been asking since 1989 should now take place, to deal with the many unanswered questions and enable the evidence which would have emerged from the now abandoned appeal to be made public." This is in sharp contrast to '''', which earlier reported that the majority of British families felt Megrahi was innocent.

The United States government had been strongly opposed to any possible release. US Secretary of State Hillary Clinton had previously called the possibility "absolutely wrong". MacAskill sought to justify the decision by commenting that "Compassion and mercy are about upholding the beliefs that we seek to live by, remaining true to our values as a people - no matter the severity of the provocation or the atrocity perpetrated."

Megrahi issued a statement shortly before leaving HMP Greenock in which he maintained his innocence. "The remaining days of my life are being lived under the shadow of the wrongness of my conviction. I have been faced with an appalling choice: to risk dying in prison in the hope that my name is cleared posthumously or to return home still carrying the weight of the guilty verdict, which will never now be lifted. The choice which I made is a matter of sorrow, disappointment and anger, which I fear I will never overcome," said Megrahi.

Robert Gibbs, press secretary for the White House, said "The United States deeply regrets the decision by the Scottish Executive to release Abdel Basset Mohamed al-Megrahi. As we have expressed repeatedly to officials of the government of the United Kingdom and to Scottish authorities, we continue to believe that Megrahi should serve out his sentence in Scotland." Many US victims have also reacted with anger. 

Many US victims' families have reacted with anger. One relative commented that "This might sound crude or blunt, but I want him returned from Scotland the same way my wife Lorraine was and that would be in a box." Dr. , a UK victim, disagreed, saying Megrahi had "nothing to do with" the disaster and calling the earlier dropping of the appeal "a blow to those of us who seek the truth."

Megrahi's plane was greeted by crowds in Tripoli waving both Libyan and Scottish flags. , son of Libyan leader , held his hand as he exited the aircraft amid heavy security. Loudspeakers broadcast patriotic music and it is reported that celebrations are ongoing in Tripoli.