The men, who are not accused of any association with Isis, were among more than 100 people to be stripped of British nationality last year as the government increased its use of the controversial power.
Their successful appeal sets a new legal precedent and could spark a more cautious approach to citizenship deprivations by the government.
It may also trigger a wave of appeals by terror suspects facing what one lawyer called “a return to the medieval penalties of banishment and exile”.
The Special Immigration and Appeals Commission allowed an appeal by two men – codenamed E3 and N3 – after closed hearings where their lawyers and government representatives battled over their status.
Allegations made by the security services were not detailed in the published judgment or shared with the men’s lawyers, who had to leave the courtroom for “closed evidence”.
The government argued they were dual British-Bangladeshi nationals, but Mr Justice Jay ruled that the deprivation orders had rendered them stateless and therefore violated international law.
E3, a 37-year-old man, was born in the UK to two Bangladeshi parents and received the order in June 2017.
He had been working in Britain to support his family in Bangladesh, and had his citizenship removed while visiting the country for the birth of his second child, his lawyers said.
In October 2017, N3 – who has three British children living in the UK – was deprived of his citizenship after travelling to Turkey for business for a few weeks, his lawyers said.
The 35-year-old was born in Bangladesh but is a British citizen by birth, and remains in Turkey.
Duncan Lewis Solicitors said both men were targeted on national security grounds days before they were due to return to the UK, and have been left “stranded in foreign countries without any source of income or support”.
The commission found that Bangladeshi law required them to apply to retain their citizenship at 21, but they failed to do so and were left with only British nationality.
Fahad Ansari, a solicitor who represented the appellants, voiced “deep concern that there appears to be an ongoing practice of the home secretary to deliberately wait until individuals leave the UK before depriving them of their citizenship”.
He argued that any suspected criminal activity should have been prosecuted in the UK, adding: “The practice of depriving individuals of their citizenship while they are abroad, without any form of due process, is nothing less than a return to the medieval penalties of banishment and exile.”
The Home Office intends to appeal the judgment and the men have put on plans to return to the UK until the case concludes.
The judgment was handed down in private on 15 November, almost a year after the government was found to have unlawfully stripped another person of Bangladeshi descent of British citizenship.
The London-born woman, known as G3, was alleged to be an Isis member and was detained by Turkish authorities on the Syrian border with her two young children in 2016.
Her deprivation order was similarly found to have rendered her stateless under international law by Mr Justice Lane.
E3, N3 and G3 were among more than 100 people deprived of UK nationality last year, as the government dramatically increased its use of the exceptional power.
In 2017, it was used to strip 104 people of their British citizenship, compared to just 14 people in 2016.
The measure has been used for high-profile terrorists, including alleged members of the British Isis cell known as the Beatles.
Alexanda Kotey and El Shafee Elsheikh, who remain imprisoned by Kurdish forces in Syria, accused the government of breaking international law and suggested they were both stateless in an interview from custody.
It is unclear whether Elsheikh, who came to the UK as a child refugee from Sudan, or London-born Kotey – who is half-Ghanaian and half-Greek Cypriot – actively held dual nationalities or will have to apply for alternative citizenship.
Elsheikh’s mother has launched a separate legal challenge over the government’s decision to hand evidence to US authorities without seeking assurances he would not be executed.
The government says stripping citizenship is “particularly important in helping prevent the return to the UK of dual-national British citizens involved in terrorism-related activity in Syria or Iraq” but the power has also been extended to lower-level extremists and criminals, including Rochdale grooming gang members.
Mr Ansari told The Independent that it was being used “more, and more widely”.
“There has been an increase in deprivation orders and the kind of cases they are being applied to – it’s not just national security,” he added.
“There is a lack of due process in the whole system … it’s the worst possible sanction to place on somebody, and trying to challenge it in this format is incredibly difficult.”
The government’s 2018 Transparency Report on Disruptive and Investigatory Powers said it “considers removal of citizenship to be a serious step, one that is not taken lightly”.
“Such action paves the way for possible immigration detention, deportation or exclusion from the UK and otherwise removes an individual’s right of abode in the UK,” it noted.
The report said the home secretary personally approves each use of the power “where it is considered that it may be conducive to the public good” over national security threats including espionage, terrorism and organised crime, or where British citizenship was obtained fraudulently.
While international law stipulates that people cannot be left stateless, the Immigration Act 2014 introduced a power allowing that to happen if a person has “acted in a manner seriously prejudicial to the vital interests of the UK”.
“This action may only be taken if the secretary of state has reasonable grounds for believing that the person is able, under the law of a country outside the UK, to become a national of that country,” the report said.
Of around 900 jihadis known to have travelled to the countries since 2014, the government estimates that 40 per cent have returned and 20 per cent have been killed in the region.
A Home Office spokesperson said: “We intend to appeal this judgment. As such, it would not be appropriate to comment further.”