Australian PM John Howard has warned Singapore that its execution of Nguyen Tuong Van may harm links between the peoples of their two countries.
Nguyen's body will be flown back to Melbourne for burial
The 25-year-old Melbourne man, of Vietnamese descent, was hanged at Changi prison before dawn as hundreds held vigils in Australia and Singapore.
Singapore's PM Lee Hsien Loong said his country had decided that "the law should take its course".
Canberra said mitigating factors should have been taken into account.
One of Nguyen's lawyers, Julian McMahon, said his client prayed until he was required to walk the 50m to the execution chamber.
He died "optimistically and with strength and died a very courageous death," Mr McMahon said.
"And I understand that as he did so other death row prisoners sang hymns and other things in various languages to support him," he added.
Nguyen's body, wrapped in a white shroud, was taken to a funeral home for embalming. His family is flying the body back to Melbourne for burial.
Australian Attorney-General Philip Ruddock told the BBC he was "terribly disappointed" by the news of the execution.
He said Nguyen always maintained he had smuggled the drugs to earn enough money to pay off legal bills of A$30,000 (£13,000) incurred by his twin brother, a former heroin addict.
Mr Ruddock reiterated his earlier comments that death by hanging was "barbaric".
John Howard said he told his Singaporean counterpart "that I believe it will have an effect on the relationship on a people-to-people, population-to-population basis."
He said he felt sympathy for Nguyen's mother, and had been disappointed by Singapore's "clinical response" to Australia's request that she be allowed to hug her son before his death. The Singapore authorities had only allowed them to hold hands.
But Mr Howard rejected calls for trade and military boycotts against Singapore, one of Australia's strongest allies in Asia.
He added that the execution should serve as a warning to other young Australians.
"Don't imagine for a moment that you can risk carrying drugs anywhere in Asia without suffering the most severe consequences," he said.
Nguyen Tuong Van was convicted three years ago of carrying nearly 400g (14 ounces) of heroin at Singapore airport while travelling from Cambodia to Australia.
Singapore has some of the strictest drug trafficking laws in the world, and anyone found with 15g of heroin faces a mandatory death penalty.
Nguyen had said he was trying to help his brother
Prime Minister Lee said Nguyen's case had been through the full legal process, and pleas for clemency by the Australian government had been considered.
But he said the case involved "an enormous amount" of drugs - the equivalent of 26,000 doses.
"We take a very serious view of drug trafficking, and the penalty is death," he said in Berlin.
A vigil by anti-death penalty campaigners took place outside the prison overnight before the dawn execution.
And hundreds of supporters gathered in Nguyen's home city of Melbourne at a church to mark the moment of his execution. A large church bell rang 25 times - once for every year of his life.
At the same time, dozens of people held a silent vigil outside the Singapore High Commission in the capital Canberra.
Nguyen was the first Australian to be executed overseas in more than a decade.