But Khadr's bid for release could be put on hold.
The Alberta Court of Appeal said in a unanimous decision Tuesday that the 27-year-old should be serving a youth sentence in Canada, and should not be in a federal prison.
Within three hours, the federal government issued a statement saying it plans to appeal the ruling and will apply to delay the transfer while it asks the Supreme Court to hear the case.
Public Safety Minister Steven Blaney said a youth sentence is not appropriate for someone such as Khadr, who "pleaded guilty to heinous crimes.
"We have vigorously defended against any attempt to lessen his punishment for these crimes," said Blaney. "That is why the government of Canada will appeal this decision and seek a stay to ensure that he stays in federal prison — where he belongs."
The Toronto-born Khadr pleaded guilty in 2010 to five war-crimes charges, including murder, for killing an American soldier in Afghanistan when he was 15. Khadr was accused of throwing a grenade that killed Sgt. Christopher Speer during a vicious battle at an Afghan compound in July 2002.
After spending a decade in Guantanamo Bay, Khadr was sentenced by a U.S. military commission to an additional eight years and sent to Canada. He has said since then that he pleaded guilty so he could get out of the Cuban detention camp.
When it sentenced him, the U.S. commission made no distinction between youth and adult punishment or between consecutive and concurrent sentences. When Khadr arrived in Canada in 2012, corrections authorities automatically took him into adult custody.
His lawyers argued that the eight-year term for crimes including murder only make sense as a youth sentence and, although he's now too old to be in a youth facility, Khadr should at least be in a provincial jail.
Lawyers for the federal government argued that the sentence of a foreign court cannot be changed and that Khadr had been given eight years as a youth for murder and the sentences on four remaining offences were to be served concurrently as an adult.
Last fall, Court of Queen's Bench Associate Chief Justice John Rooke sided with the federal government and ruled Khadr's placement in a federal prison was lawful.
The Appeal Court said he was wrong.
"We have concluded that the chambers judge erred in law in finding that Khadr was properly placed in a federal penitentiary under the ITOA (International Transfer of Offenders Act)," the court said. "We conclude that Khadr ought to have been placed in a provincial correctional facility for adults."
One of Khadr's lawyers, Nathan Whitling, said if the decision stands and Khadr gets to serve his time as a young offender, his hope for release no longer rests solely with the Parole Board of Canada. "Now he can apply to a youth court judge."
As a young offender, Khadr would get an annual review for release before a youth judge. Whitling said the judge could order his release and let him serve out his sentence in the community.
Whitling said young-offender status wouldn't necessarily help Khadr's case before the parole board. Khadr didn't apply when he was eligible for parole last year because he was still considered a maximum-security inmate.
Earlier this year, Khadr was reclassified as a medium-security federal inmate and transferred to Bowden Institution in central Alberta from Edmonton Institution. His sentence is to expire on Oct. 30, 2018.
Whitling said he spoke by phone with Khadr after the court decision and, while his client is optimistic about a transfer and eventual application for release, he's worried he won't get the chance.
The Alberta government has yet to determine any details of a transfer to provincial custody. The province's justice minister, Jonathan Denis, said his office supports the federal government's appeal and request for a stay.
Whitling said his client will ask to be moved to jail in Fort Saskatchewan, northeast of Edmonton, to be closer to his Edmonton lawyers.
One of his other lawyers, Dennis Edney, said it's important to get Khadr out of federal jurisdiction and "the hands of the Harper government."
The federal government would "rather pander to politics than apply the rule of law fairly to each and every Canadian citizen," Edney said.
"This government chose to misinterpret the International Transfer of Offenders Act and place Omar in a maximum security prison, where he spent the first seven months in solitary confinement, instead of treating him as a youth as required under both Canadian and international law."
Also on HuffPost