FERGUSON, Circuit Judge.
Salvador Rivera, a.k.a. Salvador Galvan-Gaspar, (hereinafter “Rivera”) appeals the District Court’s denial of his 28 U.S.C. § 2241 petition for a writ of habeas corpus. Rivera alleges that he is a United States citizen who was wrongly removed to Mexico, that his Due Process rights were violated during removal proceedings before Immigration Judge Anna Ho, and that he is entitled to a declaration by the District Court that he is a United States citizen. We find that the District Court has jurisdiction to hear Rivera’s citizenship claim and remand for further proceedings.
FACTUAL BACKGROUND1
Salvador Rivera was born at University North Hospital in Portland, Oregon, on January 20, 1979, to Logino Rivera and Eloísa Gaspar (now Eloísa Galvan). Approximately one month after Rivera’s birth, Eloísa obtained a certified copy of her son’s birth certificate. When Rivera was approximately three months old, Eloí-sa and Logino were having “personal problems,” so Eloísa took Rivera with her to Mexico. Eloísa and Rivera returned to the United States with Eloisa’s new husband in November 1989 when Rivera was nearly eleven years old. A few years later, Eloísa left Rivera in the United States [1131]*1131with her brother and returned to Mexico. She left Rivera’s personal documents, including those relating to his birth, with him in the United States.
INS documents indicate that on November 26, 1991, one Jorge Amaro-Gallardo and his mother, Maria De Jesus, were apprehended in a vehicle in El Centro, California. When questioned about his immigration status, Jorge gave INS agents a birth certificate that was not his own. The birth certifícate instead belonged to Salvador Rivera, born to Eloísa Gaspar and Logino Rivera on January 20, 1979, at University Hospital North in Portland, Oregon. The birth certificate had been issued on February 23,1979. Jorge Amaro-Gallardo told INS officials that the birth certificate had been “loaned” to him by an “Arturo Galvan-Aguirre.” Following this incident, the INS kept the birth certificate on file. When shown the birth certificate, Eloísa testified that it was the birth certificate that she had obtained shortly after her son’s birth and had left with Rivera when she left him with her brother and went to Mexico. She did not know why another person might have had the birth certificate. Rivera also did not know.
By the time Rivera was eighteen years old, a number of warrants existed for his arrest, so he decided to develop an alias. On a visit to his grandmother in Mexico that year, Rivera paid an unknown individual for a Mexican birth certificate. Rivera used the Mexican birth certificate to apply for a Washington driver’s license and state ID card under the name “Salvador Gal-van-Gaspar.”
On January 15, 1998, Rivera was arrested by a Border Patrol agent. Rivera believed that, due to his outstanding warrants, he would face jail or imprisonment if he gave the agent his real name. Instead, he presented himself as a Mexican citizen and underwent voluntary deportation, and then returned to the United States via Mexicali. Over a year and a half later, a Border Patrol agent interviewed Rivera at Skagit County jail in Washington. Salvador told the agent that he had previously been deported under the name Salvador Galvan-Gaspar, but that he was actually a U.S. citizen.
On December 12, 2000, Rivera was arrested by Border Patrol agents when he appeared for a parole hearing with the Washington State Department of Corrections. Rivera told the agents that he was a U.S. citizen, and that he had purchased a birth certificate in Mexico in the name of “Salvador Galvan-Gaspar.” Rivera initially agreed to give a sworn statement to the agents as to his identity, but then refused after reading the list of questions that he was to answer. That same day, the INS issued a “Notice to Appear” alleging that Rivera was not a U.S. citizen.
PROCEDURAL HISTORY
A. Immigration Court
On January 2, 2001, Rivera appeared before Immigration Judge Anna Ho. The Immigration Judge (IJ) informed Rivera that he had the right to an attorney, and asked if he needed time to find one. Rivera responded that, in 1998, he “had a lawyer, and we already fixed this matter about me being a U.S.A. citizen.” When the IJ asked Rivera whether he needed time to contact his attorney, Rivera responded, “the thing that I don’t understand is why I am here if we already — ,” at which point the IJ cut him off. Rivera presented a birth certificate indicating that he was born in Oregon on January 20, 1979, to the IJ. She informed the government lawyer that “this is obviously a true birth certificate of the respondent,” and continued the case to allow the INS time to verify Rivera’s identity. The INS lawyer said that the INS would “resolve whether we think he’s a citizen” before the case resumed.
[1132]*1132The INS, however, did not resolve its position. When the parties reappeared before IJ Ho six days later, the INS lawyer told the IJ, “I don’t know whether or not that birth certificate relates to him or not. I think it’s a question of fact for the Court.” The INS lawyer further stated that if Rivera “is a citizen, he is, of course, not removable from the United States. But he has created this situation by assuming a false identity as an illegal alien and taking a removal order or voluntary departure once before.” The IJ then told Rivera that his case would be set over to January 30, 2001, and that he “may have your family come in and testify and bring in all the proof to state that you are a U.S. citizen.” The IJ also told Rivera, “You need to bring in people that knew you were born and knew your name.”
At the January 30 hearing, the government’s position was that Rivera had agreed to “removal to Mexico under one name and now asserts to be a citizen and produces a birth certificate which may or may not be his, may or may not relate to him. But we do know that there was another instance that some person ... has used it also.” The INS presented testimony from two Border Control agents, who said that Rivera told them that he had undergone voluntary removal to Mexico before but that he was actually a U.S. citizen. The INS also presented documents relating to Rivera’s removal to Mexico, his subsequent INS contacts, the fraudulent use of the Oregon birth certificate by Jorge Amaro-Gallardo in 1991, a driver’s license and state ID card for “Salvador Galvan-Gaspar,” and a driver’s license for “Salvador Rivera.” The INS stated that there was no death record for “Salvador Rivera.”
Eloísa gave the IJ a packet of paperwork relating to Rivera. In addition to the birth certificate, the paperwork included a February 5, 1993 progress report for “Salvador Rivera” from LaVenture Middle School; a page from a high school yearbook picturing “Salvador Rivera” as a sophomore student; a tax return prepared for “Salvador Rivera” by H & R Block for the .1998 tax year (including W-2 forms indicating that Salvador Rivera was employed by “Larry Vander Veen” and “Draper Valley Farms”); and a police file photo indicating that “Salvador Rivera” was also known as “Salvador Galvan”. The IJ responded:
I have a lot of questions and a lot of problems with just a live certificate, which doesn’t tell me anything, because anyone could go get a copy of a birth certificate. So I need a lot more proof than just a birth certificate and a picture, which is an adult picture.
You’ve provided a photograph of a high school album. That doesn’t mean anything. Any — people who have no documents can go to high school here, so that doesn’t mean you’re a U.S. citizen.
... You know, if you’re a U.S. citizen, you certainly- — your mother certainly would have more than just this for record. My children were born in this country. I could trace them from their birth ... all the way up to their adult age. And you have nothing here to show that.
The IJ put both Rivera and Eloísa on the stand; both testified as previously described. The IJ questioned Eloísa particularly closely about the time she went to Mexico without Rivera and left him in her brother’s care.2 First, the IJ asked, “And [1133]*1133when was it that you left for Mexico by yourself?” Eloísa responded that she could not “remember the year exactly.” The IJ asked, “Well, how old was your son when you left for Mexico by yourself?” Eloísa answered, “I don’t remember if he was 14 or less or more. I don’t remember.”
A few questions later, the IJ asked, “And at that time he was already 14 years old?” Eloísa said, “I don’t remember if he was already 14 by then. I’m not sure.” The IJ persisted: “But approximately when he was 14 years old; is that right?” Eloísa agreed.
The IJ returned to the topic again: “And you said you went to Mexico without your son when he was about 14; is that right?” Eloísa replied, “Yes.” The IJ said, “Okay. And in 1993, your son was 14, right?” Eloísa responded affirmatively.
After a court break, the IJ brought the question up a fourth time: “So it was in 1993 that you gave your son’s birth certificate with his footprint to him?” Eloísa responded, “I don’t remember. But I did give it to him after he stayed behind.” The IJ said, “And that was when he was about 14, is that right?” Eloísa agreed. The IJ said, “And if you and I calculate it right, it was about 1993; isn’t that correct?” Eloísa again agreed.
After the INS had had an opportunity to question Eloísa, the IJ asked the government for its position on the case. The INS said that Rivera had “failed to ... successfully rebut the Service’s evidence that he is, in fact, a native and citizen of Mexico.” The IJ said that she agreed that Rivera had “not provided sufficient evidence to prove that you are, indeed, a U.S. citizen.” In her view, the “most important thing” was
the fact that your mother testified that she never let the birth certificate out of her sight — your birth certificate — until 1993. And somehow, somebody else had your birth certificate in 1991. So I don’t know who is not telling me the truth but, certainly, this is not the truth. And you have not met your burden that you are a U.S. citizen.
Having ruled, the IJ informed Rivera, “you certainly have a right to appeal from my decision, and you may do so. I can only tell you that the appeal process will take ... five months or maybe more.” Rivera said, “I don’t really understand what appeal or — .” The IJ said, “Appeal means that you want another Court to review the tapes and the all the [sic] documents in your file to see if I’ve made a right decision.” Rivera responded, ‘Tes.”
Approximately one week later, however, Rivera agreed to waive his appeal. Present counsel for Rivera contends that Rivera did so because he believed that “seeking help from ‘another court’ such as the one he had just experienced” would be futile, and because he believed he would have to remain in INS custody while his appeal was pending. Rivera was subsequently deported to Mexico.
B. District Court
On March 11, 2003, Rivera filed a Petition for Writ of Habeas Corpus and a Complaint for Declaratory Judgment and Order to Show Cause with the District Court. After supplemental briefing and oral argument on the issue of jurisdiction, the District Court issued a judgment that it lacked habeas jurisdiction over Rivera’s case. The District Court found that 8 U.S.C. § 1252 provided an exclusive remedy for judicial review of nationality claims, that Rivera was not in custody within the jurisdiction of the Court, and that Rivera had not exhausted his administrative remedies. The District Court stated that, in so holding, it was following our precedent in Taniguchi v. Schultz, 303 F.3d 950 (9th Cir.2002), and Miranda v. Reno, 238 F.3d [1134]*11341156 (9th Cir.2001). The District Court also held that “extreme circumstances” would permit the exercise of habeas jurisdiction, but that such circumstances were not present in Rivera’s case because he was told that he could have an attorney and told that he had the right to appeal.
DISCUSSION
We review a district court’s dismissal of a § 2241 petition for lack of jurisdiction de novo. See Miranda v. Reno, 238 F.3d at 1158.
We begin our analysis with some scrutiny of the facts and procedural history of this case.
First, the INS did not present its own version of the facts of Rivera’s birth, presumably because, on the evidence before the IJ, there was no other version that was plausible. No party has disputed that the Oregon birth certificate is an authentic State document; the only question is whether it belongs to Rivera or to some other person. The Mexican birth certificate is too similar to the Oregon birth certificate to also be authentic. The birth dates are the same, the mother’s name (Eloisa Gaspar) is the same, and the first name “Salvador” is the same. Moreover, the other last name on the Mexican birth certificate, Galvan, is Eloisa’s married name. If it were the INS’s position that the Mexican document was Rivera’s real birth certificate, and the Oregon birth certificate belonged to someone else, the coincidences would be staggering. The INS story would have to be that Mexican citizens “Eloisa Gaspar” and her son, “Salvador Galvan-Gaspar,” went to the United States and discovered that another woman named “Eloisa Gaspar” had a son named “Salvador Rivera” born in Oregon on exactly the same date, and contrived to obtain “Salvador Rivera’s” birth certificate. This set of circumstances is not out of the realm of imagination, but it is incredibly unlikely. Far more plausible is the explanation that the Oregon birth certificate belongs to Rivera, and that he simply had a Mexican birth certificate created with his own birthdate and own mother on it, but changed his last name to his mother’s married name.3
In bringing this case to Immigration Court, the INS also took no position as to whether the Oregon birth certificate did in fact belong to Rivera. This is a startling posture given that, if the Oregon birth certificate is Rivera’s, he is an American citizen. The INS did little even to investigate whether the Oregon birth certificate was Rivera’s aside from checking whether a death record existed under the name “Salvador Rivera” (it did not). Instead, the INS came before the IJ with the position that it did not know whether Rivera was a citizen. As an agency of the United States, the INS ought to have been just as zealous in making sure that U.S. citizens were not unlawfully removed from the United States as they were in making sure that illegal immigrants were excluded. Why they would not have resolved to their own satisfaction whether or not Rivera was a U.S. citizen is difficult to fathom. As we stated in Sun Il Yoo v. INS, 534 F.2d 1325, 1329 (9th Cir.1976), “When such serious injury [ie., deportation] may be [1135]*1135caused by INS decisions, its officials must be held to the highest standards in the diligent performance of their duties. Here, their duty was clear.” Such overreaching by the INS could have been cured by the IJ at the time that government counsel admitted that the INS did not know whether the Oregon birth certificate belonged to Rivera. Instead, Immigration Judge Ho essentially allowed the INS to use her as its investigative agent.
Both the decision issued by the IJ and her conduct of the hearing demonstrate that “the IJ did not conduct herself as an impartial judge but rather as a prosecutor anxious to pick holes in the petitioner’s story.” Li v. Ashcroft, 378 F.3d 959 (9th Cir. Aug. 5, 2004) (Noonan, J., dissenting). In deciding that Rivera was not a citizen, the IJ said that the most important factor was that Eloísa had testified that she had not let Rivera’s birth certificate “out of her sight” until 1993, but that someone else had the birth certificate in 1991. The IJ concluded that someone “is not telling me the truth.” The reality is that Eloísa repeatedly stated that she did not recall what year she had left for Mexico and given Rivera his birth certificate; she only agreed to 1993 at the repeated pushing of the IJ. Jorge Amaro-Gallardo attempted to use Rivera’s birth certificate on November 26, 1991; at that time, Rivera would have been nearly thirteen. That is not enough to make Eloisa’s statements “I don’t know if he was 14 or less or more” and “I don’t remember if he was already 14 by then” into lies.
The other apparent basis for the IJ’s ruling was that she found Rivera’s documentary evidence inadequate. Immigration Judge Ho dismissed Rivera’s birth certificate as evidence “because anyone could go get a copy of a birth certificate.” She dismissed his high school yearbook and middle school record because “people who have no documents can go to ... school here.” She dismissed his other documents, presumably including his tax and employment records, because they related to his adult life. One wonders what other sort of documentation than a birth certificate, school records, and “adult” documents such as tax returns and state ID cards or driver’s licenses the IJ would have expected to see.4 Moreover, the IJ compared her own preservation of her children’s paperwork with Eloisa’s (“My children were born in this country. I could trace them from their birth ... all the way up to their adult age.”). There is no reason that a seasonal worker such as Eloísa would have had the ability to preserve her children’s paperwork to the extent that a civil service professional would have been able to do.
We also note a bizarre colloquy between the IJ and Eloísa, in which the IJ accuses Eloísa of lying when she said that she left her son for the first time when she went to Mexico in 1993, because Eloísa also said that she took Rivera with her to Mexico when he was three months old:
Q If I were to tell you, sir, that— ma'am, that your son testified that he went to Mexico when he was three months old, is he lying?
A No. He’s not lying, because he was in Mexico at that age.
Q Well, ma'am, you said you never left your son until he was 14 years old.
A I didn’t leave him. He went with me.
Q Well, ma'am, you said you left your son the first time when he was 14 years old in 1993. You just told me that earlier. And I asked you that [1136]*1136three times, so were you lying'to me earlier?
A Well, I didn’t understand, then, because I said that I had never left him before.
Q Well, I asked you if you ever left your son for Mexico, and you said you left him alone here, when you went to Mexico. You never said you went to Mexico with him when he was three months old.
A I understood that if I had left him here in the United States, and I did leave him here when he was 14, but not before that. I didn’t say that I’d left him before that.
Q Ma'am, my question originally to you was have you ever left your son since his birth, and you said that you left him when he was 14 years old when you went to Mexico.
A Yes. He stayed here with my brother.
Q You never said that you took your son with you when he was three months old to Mexico.
A No. I took him with me. He was born here in Portland, and when I went to Mexico, I took him with me to Mexico.
Eloisa’s testimony had been that she took her son with her to Mexico when he was three months old, and that she left him (for the first time) in the United States in the care of her brother when Rivera was approximately fourteen years old and went to Mexico by herself. There is nothing contradictory in these statements, and no basis for the IJ’s impression that Eloísa was lying to her.
I. Habeas Review
The executive may deport certain aliens but has no authority to deport citizens. An assertion of U.S. “citizenship is thus a denial of an essential jurisdictional fact” in a deportation proceeding. Ng Fung Ho v. White, 259 U.S. 276, 284, 42 S.Ct. 492, 66 L.Ed. 938 (1922); see also Frank v. Rogers, 253 F.2d 889, 890 (D.C.Cir.1958) (“Until the claim of citizenship is resolved, the propriety of the entire proceeding is in doubt.”).
Because the deportation of “one who so claims to be a citizen obviously deprives him of liberty ... [and] may result also in loss of both property and life, or of all that makes life worth living,” the Fifth Amendment mandates that any person with a non-frivolous claim to American citizenship receive a judicial evaluation of that claim.5 Ng Fung Ho, 259 U.S. at 284-85, 42 S.Ct. 492. In Ng Fung Ho, the Supreme Court found that this constitutional right would be violated by the deportation of two men following executive proceedings, and directed that writs of ha-beas corpus issue to permit federal district court review of their citizenship claims. Id.
Here, the government contends that the writ may not issue because Rivera waived his right to appeal the IJ’s ruling and was deported. As a result, Rivera is no longer “in custody”; nor has he exhausted administrative remedies or pursued a direct appeal under 8 U.S.C. § 1252 — which statute, according to the government, provides an exclusive judicial remedy. However, if Rivera is in fact a U.S. citizen, permitting the IJ’s determination that he is not a citizen to stand renders Rivera a stateless person. If the government’s analysis of this case were correct, it would be possible to unintentionally relinquish U.S. citizenship by waiving the right to appeal a deportation order.
The Constitution does not permit American citizenship to be so easily shed. Under the Fourteenth Amendment, all [1137]*1137people born in the United States are citizens of the United States. United States v. Wong Kim Ark, 169 U.S. 649, 702, 18 S.Ct. 456, 42 L.Ed. 890 (1898). The citizenship defined by the Amendment is one “which a citizen keeps unless he voluntarily relinquishes it.” Afroyim v. Rusk, 387 U.S. 253, 262, 87 S.Ct. 1660, 18 L.Ed.2d 757 (1967). This rule has its root in the fact that “[i]n our country the people are sovereign and the Government cannot sever its relationship to the people by taking away their citizenship.” Id. at 257, 87 S.Ct. 1660; see also Nishikawa v. Dulles, 356 U.S. 129, 138-39, 78 S.Ct. 612, 2 L.Ed.2d 659 (1958) (Black, J., concurring) (explaining that the rule that citizens may hot be involuntarily expatriated “results not only from the provisions of the Fourteenth Amendment but from the manner in which the Government of the United States was formed, the fundamental political principles which underlie its existence, and its continuing relationship to the citizenry who erected and maintain it.”).
In Vance v. Terrazas, 444 U.S. 252, 260, 100 S.Ct. 540, 62 L.Ed.2d 461 (1980), the Supreme Court explained that its holding in Afroyim precluding involuntary relinquishment of citizenship meant that a person losing citizenship must intend to do so, “whether the intent is expressed in words or is found as a fair inference from proved conduct.” The Court held that it was therefore not sufficient for the government to prove that, by making a formal declaration of allegiance to a foreign state, Terrazas had voluntarily committed an act designated as expatriating by Congress. Terrazas, 444 U.S. at 255, 261, 100 S.Ct. 540. For Terrazas to lose his U.S. citizenship, the government had to prove that, in swearing allegiance to Mexico, he “also intended to relinquish his citizenship.” Id. at 261, 100 S.Ct. 540.
In short, a U.S. citizen cannot lose that status unless the government can prove that the person intended to relinquish citizenship. We can think of no reason why citizens illegally deported by the government should be exempt from that rule. Acceptance of deportation after an administrative hearing is not, in and of itself, proof that a person wishes to relinquish citizenship. Such acceptance cannot serve to conclusively establish a person’s non-citizen status when that person makes a non-frivolous claim to U.S. citizenship. Because he has a colorable citizenship claim, Rivera has a constitutional right to judicial review, and may obtain such review via habeas corpus even after accepting deportation and waiving his right to appeal the IJ’s decision.
Our case law is not to the contrary. Prior to the passage of the Illegal Immigration Reform and Immigrant Responsibility Act of 1996 (IIRIRA), Pub.L. 104-208, 110 Stat. 3009 (Sept. 30, 1996), a petition for a writ of habeas corpus could be brought in federal district court pursuant to 8 U.S.C. § 1105a(b) or 28 U.S.C. § 2241. Section 1105a was repealed by IIRIRA. However, IIRIRA did not repeal the statutory habeas corpus remedy provided by § 2241. INS v. St. Cyr, 533 U.S. 289, 314, 121 S.Ct. 2271, 150 L.Ed.2d 347 (2001); Angulo-Dominguez v. Ashcroft, 290 F.3d 1147, 1149 (9th Cir.2002).
In Magana-Pizano v. INS, 200 F.3d 603, 608 (9th Cir.1999) (on remand from the Supreme Court), we stated that we adhered to our prior result in Maganar-Pizano v. INS, 152 F.3d 1213 (9th Cir. 1998) that § 2241 is available when an alien in custody pursuant to an order of deportation has no other remedy. In Taniguchi, 303 F.3d at 955, we noted that statement and proceeded to hold that the remedy provided by § 1252(b)(5), which permits direct appeal from Board of Immigration Appeals (BIA) determinations to the Court of Appeals on questions of na[1138]*1138tionality, is an exclusive remedy for aliens in removal proceedings with citizenship claims. Like Rivera, Taniguchi could have appealed the issue of her nationality directly to .the Court of Appeals pursuant to § 1252(b)(5) but did not do so. See id. at 956. We held that habeas relief was therefore not available to her. Id. at 955. The District Court believed that this holding in Taniguchi controlled the outcome of Rivera’s case.
Taniguchi, however, did not involve the Fifth and Fourteenth Amendment issues presented here because Taniguchi’s claim to U.S. citizenship was patently frivolous. She was a native and citizen of the Philippines and had a conviction for impersonating a citizen of the United States. Id. at 953. Her claim to citizenship had no greater foundation than the fact that she had applied for a certificate of citizenship on a federal form. Id. at 954. She did not even bother to raise her frivolous citizenship claim in her removal hearing before the Immigration Judge. Id. at 955.
The Fifth Amendment right to judicial review of non-frivolous citizenship claims and the Fourteenth Amendment right to U.S. citizenship (absent voluntary relinquishment) are not violated when an alien making a frivolous citizenship claim is deported after administrative proceedings. Taniguchi’s deportation was therefore not in conflict with these constitutional rights. Rivera’s citizenship claim is at the opposite end of the spectrum from Taniguchi’s. The only result consistent with the Fifth and Fourteenth Amendments is that habeas relief be available to hear Rivera’s citizenship claim.
Our decision in Miranda v. Reno is also not in conflict with our holding in this case. Citing § 2241’s requirements that a petitioner must be “in custody,” we held in Miranda that a petitioner who has already been removed “cannot avail himself of ha-beas corpus jurisdiction.” 238 F.3d at 1158. We also noted an exception to this rule: “under extreme circumstances,” we have held that an immigrant already removed may still receive habeas review. Id. at 1159.
The extreme circumstances exception arose in our decision in Singh v. Waters, 87 F.3d 346 (9th Cir.1996). The INS had removed Singh in violation of a stay of deportation by the immigration judge and after interfering with Singh’s right to counsel. Id. at 349. We held that, in such a case, Singh could not be considered to have “departed” the United States and was thus still in custody. Id. Such extreme circumstances did not exist in Miranda. 238 F.3d at 1159. Miranda was removed “after a hearing at which he was represented by counsel. His counsel waived Miranda’s right to appeal that order to the Board of Immigration Appeals.” Id. Moreover, after deportation, Miranda was “subject to no greater restraint than any other non-citizen living outside American borders.” Id.
The facts of Miranda are not analogous to the facts of this case. Unlike Rivera, Miranda was represented by counsel before his hearing before an immigration judge. Miranda’s waiver of the right to appeal to BIA was also made with the aid of counsel. Finally, Miranda had no claim to being an American citizen. If, as Rivera plausibly contends, he is a citizen forced to live outside U.S. borders, he is clearly subject to greater restraints than other citizens.
The District Court believed that the facts of this case do not rise to the level of extreme circumstances warranting issuance of a writ of habeas corpus because Rivera was told of his right to counsel as well as of his right to an appeal. We disagree. In Singh, we held that, because the government had “effectively scuttled the right to counsel guaranteed to Singh [1139]*1139by statute,” his deportation was unlawful and he could not be considered to have departed the country. 87 F.3d at 349. Rivera’s rights to judicial review of his citizenship claim and to U.S. citizenship (if he is a citizen) are guaranteed to him by the Constitution. The government would be able to very effectively sink these rights if its deportation of Rivera could prevent further review of his citizenship claim. For the purposes of habeas review, Rivera, like Singh, cannot be considered to have departed the country.
In Singh, we observed that “Singh was not traveling out of the country of his own volition. He had been put on the plane deporting him by an officer of the INS.” Id. at 349. The fact that Rivera acquiesced in his own deportation does not affect our analysis because the waiver of his appeal rights was not made knowingly or voluntarily. The IJ told Rivera only that “[ajppeal means that you want another Court to review the tapes and the all the [sic ] documents in your file to see if I’ve made a right decision.” She did not tell him that, because he had a plausible claim to U.S. citizenship, he had a constitutional right to judicial (and not merely administrative) review of that claim. Nor did she tell Rivera that, if he were in fact a citizen, failing to appeal would amount to relinquishment of his citizenship because her determination that he was not a citizen would become final.
Moreover, the abuse of executive power exhibited here rises to the level of Singh. The INS prosecuted its deportation claim against Rivera without resolving whether the Oregon birth certificate belonged to him, and the IJ allowed herself to be used as the INS’s investigative agent rather than acting as an impartial fact-finder. During the deportation hearing, the IJ dismissed out of hand Rivera’s birth certificate, school records, and tax documents because they were a less complete record than the IJ would have been able to generate for her own children. The IJ’s conclusion that Rivera was not a citizen was made on the basis of an imaginary contradiction in testimony, manufactured by the IJ herself. These abuses of executive power, the unknowing and involuntary nature of the waiver of appeal, and the fact that the Fourteenth Amendment does not permit involuntary relinquishment of citizenship all support our finding of extreme circumstances sufficient to permit a writ of habeas corpus in this case.
This decision is not in conflict with our jurisprudence regarding exhaustion of remedies. In Castro-Cortez v. INS, 239 F.3d 1037, 1047 (9th Cir.2001), we observed that exhaustion was not required by § 2241 and that, in Brown v. Rison, 895 F.2d 533, 535 (9th Cir.1990), we had held that exhaustion “is not a ‘jurisdictional’ prerequisite” of § 2241. In Brown, we held that a petitioner’s failure to exhaust his administrative remedies before pursing habeas review “does not divest us of jurisdiction,” and that “[wjhere exhaustion of administrative remedies is not jurisdictional, the district court must determine whether to excuse the faulty exhaustion and reach the merits, or require the petitioner to exhaust his administrative remedies before proceeding in court.” 895 F.2d at 535.
More recently, in Sun v. Ashcroft, 370 F.3d 932, 941 & n. 13 (9th Cir.2004), we held that § 1252(d)(1) establishes a statutory administrative, but not judicial, exhaustion requirement. We applied this ruling to Sun, a Cambodian refugee ordered removed on the basis of a firearm conviction, and affirmed the district court’s denial of Sun’s petition for habeas corpus. Id. at 934-35, 945. However, our disposition of the case also relied on our finding that “[n]o constitutional violation would arise from Sun’s removal.” Id. at 945. By [1140]*1140contrast, the Constitution is violated when a person with a non-frivolous claim to U.S. citizenship is deported without receiving a judicial determination of that claim. The statutory administrative exhaustion requirement of § 1252(d)(1) does not apply in such a case.
Finally, the dissent contends that Rivera can seek alternative relief by obtaining a certificate of identity from a diplomatic or consular officer in accordance with 8 U.S.C. § 1503(b). But such relief would prove ineffective for Rivera. Even with a certificate of identity in hand, Rivera would need to apply for separate admission to the United States under 8 U.S.C. § 1503(c). That provision confirms the ability of the Attorney General to deny persons with properly obtained certificates of identity entry into the United States. Thus, were Rivera to obtain a certificate of identity and then present himself for entry into the United States, the Attorney General would deny his entry on the basis of the IJ’s determination that Rivera was not a citizen. On habeas review, the questions then before the reviewing court would be whether or not the IJ had so determined (which she has) and whether or not the IJ’s order was final (which it would be). The court in that proceeding could not reevaluate the merits of Rivera’s claim to be a United States citizen, nor evaluate whether Rivera’s Due Process rights had been violated in the first hearing.
Rivera is no model citizen. By his own account, he procured false documents and lied to Border Patrol officials in order to evade warrants for his arrest. But the punishment for this sort of fraud is provided in federal statutes, and it does not include banishment from the United States or involuntary relinquishment of citizenship. As Chief Justice Warren observed in Trop v. Dulles, 356 U.S. 86, 92, 78 S.Ct. 590, 2 L.Ed.2d 630 (1958) (plurality opinion), “[cjitizenship is not a license that expires upon misbehavior.” We reverse the District Court’s denial of Rivera’s petition for habeas corpus and remand for further proceedings.
Only the issue of jurisdiction was decided by the District Court and this Court. Accordingly, nothing in this opinion should be construed as rendering any findings of fact as to Rivera’s citizenship, which is a question the District Court should address in the first instance.
REVERSED AND REMANDED.