FOR PUBLICATION
  UNITED STATES COURT OF APPEALS
       FOR THE NINTH CIRCUIT

SALVADOR RIVERA,                                No. 03-35548
               Plaintiff-Appellant,
                                                    D.C. No.
               v.
JOHN ASHCROFT, Attorney General;               CV-03-00634-TSZ
                                                 ORDER AND
IMMIGRATION AND NATURALIZATION
                                                  AMENDED
SERVICE,
                                                   OPINION
            Defendants-Appellees.
                                          
         Appeal from the United States District Court
           for the Western District of Washington
          Thomas S. Zilly, District Judge, Presiding

                    Submitted June 7, 2004*
                      Seattle, Washington

                     Filed October 18, 2004
                    Amended January 7, 2005

      Before: Harry Pregerson, Warren J. Ferguson, and
           Consuelo M. Callahan, Circuit Judges.

                  Opinion by Judge Ferguson;
                   Dissent by Judge Callahan




  *This panel unanimously finds this case suitable for decision without
oral argument. See Fed. R. App. P. 34(a)(2).

                                 181
184                  RIVERA v. ASHCROFT


                         COUNSEL

Cheryl M. Nance, Bell, Flegenheimer & Nance, Seattle,
Washington; Karen L. Gilbert, for the plaintiff-appellant.

Kirsten M. Schimpff, United States Attorney’s Office, Seattle,
Washington, for the defendants-appellees.


                          ORDER

  The opinion filed October 18, 2004, 

(9th Cir.
2004), is hereby amended. The amended opinion is filed con-
currently with this order.


                         OPINION

FERGUSON, Circuit Judge:

   Salvador Rivera, a.k.a. Salvador Galvan-Gaspar, (hereinaf-
ter “Rivera”) appeals the District Court’s denial of his 28
                        RIVERA v. ASHCROFT                       185
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 Dis-
trict 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
Eloisa Gaspar (now Eloisa Galvan). Approximately one
month after Rivera’s birth, Eloisa obtained a certified copy of
her son’s birth certificate. When Rivera was approximately
three months old, Eloisa and Logino were having “personal
problems,” so Eloisa took Rivera with her to Mexico. Eloisa
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, Eloisa left Rivera in the United
States with her brother and returned to Mexico. She left Rive-
ra’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 ques-
tioned about his immigration status, Jorge gave INS agents a
birth certificate that was not his own. The birth certificate
instead belonged to Salvador Rivera, born to Eloisa Gaspar
and Logino Rivera on January 20, 1979, at University Hospi-
tal 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
  1
   What follows is the story to which Rivera and his mother testified
before the Immigration Judge, unless otherwise noted.
186                   RIVERA v. ASHCROFT
an “Arturo Galvan-Aguirre.” Following this incident, the INS
kept the birth certificate on file. When shown the birth certifi-
cate, Eloisa 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 Mex-
ico. 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 certif-
icate. Rivera used the Mexican birth certificate to apply for a
Washington driver’s license and state ID card under the name
“Salvador Galvan-Gaspar.”

   On January 15, 1998, Rivera was arrested by a Border
Patrol agent. Rivera believed that, due to his outstanding war-
rants, he would face jail or imprisonment if he gave the agent
his real name. Instead, he presented himself as a Mexican citi-
zen 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.
                      RIVERA v. ASHCROFT                     187
                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 certifi-
cate 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.

   The 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 citi-
zen, 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
188                     RIVERA v. ASHCROFT
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.”

   Eloisa 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 year-
book 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 Salva-
dor Rivera was employed by “Larry Vander Veen” and “Dra-
per 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 any-
      thing, 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 pic-
      ture.

        ...

         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.
                         RIVERA v. ASHCROFT                          189
      . . . 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 coun-
      try. 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 Eloisa on the stand; both testi-
fied as previously described. The IJ questioned Eloisa particu-
larly closely about the time she went to Mexico without
Rivera and left him in her brother’s care.2 First, the IJ asked,
“And when was it that you left for Mexico by yourself?”
Eloisa 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?” Eloisa 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?” Eloisa 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?”
Eloisa 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?” Eloisa replied, “Yes.” The IJ said, “Okay. And in
1993, your son was 14, right?” Eloisa responded affirma-
tively.

   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 certifi-
cate with his footprint to him?” Eloisa 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?” Eloisa agreed. The IJ said, “And if you and I calculate
  2
   We quote from this colloquy at length because it served as the primary
basis for the IJ’s decision.
190                     RIVERA v. ASHCROFT
it right, it was about 1993; isn’t that correct?” Eloisa again
agreed.

   After the INS had had an opportunity to question Eloisa,
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 pro-
vided 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 cer-
      tificate — 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] docu-
ments in your file to see if I’ve made a right decision.” Rivera
responded, “Yes.”

  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
                      RIVERA v. ASHCROFT                     191
and Order to Show Cause with the District Court. After sup-
plemental briefing and oral argument on the issue of jurisdic-
tion, 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, 

(9th Cir. 2002), and
Miranda v. Reno, 

(9th Cir. 2001). The District
Court also held that “extreme circumstances” would permit
the exercise of habeas jurisdiction, but that such circum-
stances 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. 

.

  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 authen-
tic. 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 cer-
tificate, Galvan, is Eloisa’s married name. If it were the INS’s
position that the Mexican document was Rivera’s real birth
192                       RIVERA v. ASHCROFT
certificate, and the Oregon birth certificate belonged to some-
one 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 certifi-
cate 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 mar-
ried 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 Ore-
gon 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
  3
    It would require fewer coincidences to believe that Rivera’s and his
mother’s names were something else entirely, and that, upon entering the
United States, they obtained an Oregon birth certificate for “Salvador
Rivera” and have been passing themselves off as “Salvador Rivera” and
“Eloisa Gaspar” since Rivera was in middle school. If that were the INS’s
story, however, there is no evidence that it might be true: the INS evidence
related to the Mexican birth certificate and Rivera’s temporary claim to
that identity. The INS was able to show that someone else tried to use the
Oregon birth certificate, but that is not at all probative of whether it
belonged to Rivera.
                      RIVERA v. ASHCROFT                     193
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, 

, 1329 (9th Cir.
1976), “When such serious injury [i.e., deportation] may be
caused by INS decisions, its officials must be held to the high-
est 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, No. 02-72689,
slip op. at 10495 (9th Cir. Aug. 5, 2004) (Noonan, J., dissent-
ing). In deciding that Rivera was not a citizen, the IJ said that
the most important factor was that Eloisa 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 Eloisa 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 push-
ing 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. Immigra-
tion 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
194                       RIVERA v. ASHCROFT
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 docu-
mentation 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
Eloisa 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 Eloisa,
in which the IJ accuses Eloisa of lying when she said that she
left her son for the first time when she went to Mexico in
1993, because Eloisa 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.
  4
    Certainly, the instructions given to Rivera before the hearing by the IJ
would have led him to think that this sort of documentation was adequate
(e.g., “You need to bring in people that knew you were born and knew
your name.”).
                     RIVERA v. ASHCROFT                      195
    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 three
        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
196                      RIVERA v. ASHCROFT
in these statements, and no basis for the IJ’s impression that
Eloisa was lying to her.

I.       Habeas Review

   [1] 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 deporta-
tion proceeding. Ng Fung Ho v. White, 

, 284
(1922); see also Frank v. Rogers, 

, 890 (D.C.
Cir. 1958) (“Until the claim of citizenship is resolved, the pro-
priety of the entire proceeding is in doubt.”).

   [2] 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 

. 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 habeas corpus issue to permit federal district court
review of their citizenship claims. 

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, accord-
ing 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 relin-
     5
   In so holding, the Court adverted to the greater protection afforded by
judicial over administrative action. Ng Fung 

.
                      RIVERA v. ASHCROFT                     197
quish U.S. citizenship by waiving the right to appeal a depor-
tation order.

   [3] The Constitution does not permit American citizenship
to be so easily shed. Under the Fourteenth Amendment, all
people born in the United States are citizens of the United
States. United States v. Wong Kim Ark, 

, 702
(1898). The citizenship defined by the Amendment is one
“which a citizen keeps unless he voluntarily relinquishes it.”
Afroyim v. Rusk, 

, 262 (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 peo-
ple by taking away their citizenship.” 

see also
Nishikawa v. Dulles, 

, 138-39 (1958) (Black, J.,
concurring) (explaining that the rule that citizens may not 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 funda-
mental political principles which underlie its existence, and its
continuing relationship to the citizenry who erected and main-
tain it.”).

   In Vance v. Terrazas, 

, 260 (1980), the
Supreme Court explained that its holding in Afroyim preclud-
ing 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. 

, 261. 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.” 

  [4] In short, a U.S. citizen cannot lose that status unless the
government can prove that the person intended to relinquish
198                   RIVERA v. ASHCROFT
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, 

, 314 (2001); Angulo-Dominguez v. Ashcroft, 

, 1149 (9th Cir. 2002).

   In Magana-Pizano v. INS, 

, 608 (9th Cir.
1999) (on remand from the Supreme Court), we stated that we
adhered to our prior result in Magana-Pizano v. INS, 

(9th Cir. 1998) that § 2241 is available when an alien in
custody pursuant to an order of deportation has no other rem-
edy. In 

, 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 nationality, 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 

We held that
habeas relief was therefore not available to her. 

                       RIVERA v. ASHCROFT                     199
The District Court believed that this holding in Taniguchi
controlled the outcome of Rivera’s case.

   Taniguchi, however, did not involve the Fifth and Four-
teenth 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. 

Her
claim to citizenship had no greater foundation than the fact
that she had applied for a certificate of citizenship on a federal
form. 

She did not even bother to raise her frivolous
citizenship claim in her removal hearing before the Immigra-
tion Judge. 

   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 him-
self of habeas corpus 

. We also
noted an exception to this rule: “under extreme circum-
stances,” we have held that an immigrant already removed
may still receive habeas review. 

   The extreme circumstances exception arose in our decision
in Singh v. Waters, 

(9th Cir. 1996). The INS had
removed Singh in violation of a stay of deportation by the
200                   RIVERA v. ASHCROFT
immigration judge and after interfering with Singh’s right to
counsel. 

We held that, in such a case, Singh could
not be considered to have “departed” the United States and
was thus still in custody. 

circumstances did
not exist in 

. 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.” 

deporta-
tion, Miranda was “subject to no greater restraint than any
other non-citizen living outside American borders.” 

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 citi-
zen forced to live outside U.S. borders, he is clearly subject
to greater restraints than other citizens.

   [5] The District Court believed that the facts of this case do
not rise to the level of extreme circumstances warranting issu-
ance 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 dis-
agree. In Singh, we held that, because the government had
“effectively scuttled the right to counsel guaranteed to Singh
by statute,” his deportation was unlawful and he could not be
considered to have departed the 

. Rive-
ra’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 effec-
tively sink these rights if its deportation of Rivera could pre-
vent further review of his citizenship claim. For the purposes
of habeas review, Rivera, like Singh, cannot be considered to
have departed the country.

  [6] In Singh, we observed that “Singh was not traveling out
of the country of his own volition. He had been put on the
                      RIVERA v. ASHCROFT                     201
plane deporting him by an officer of the INS.” 

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 “[a]ppeal 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 constitu-
tional 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.

   [7] 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 citi-
zen 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,

, 1047 (9th Cir. 2001), we observed that
exhaustion was not required by § 2241 and that, in Brown v.
Rison, 

, 535 (9th Cir. 1990), we had held that
exhaustion “is not a ‘jurisdictional’ prerequisite” of § 2241. In
202                   RIVERA v. ASHCROFT
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 “[w]here 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 

.

   [8] More recently, in Sun v. Ashcroft, 

, 941 &
n.13 (9th Cir. 2004), we held that § 1252(d)(1) establishes a
statutory administrative, but not judicial, exhaustion require-
ment. 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. 

945. However, our disposition of the
case also relied on our finding that “[n]o constitutional viola-
tion would arise from Sun’s removal.” 

By contrast,
the Constitution is violated when a person with a non-
frivolous claim to U.S. citizenship is deported without receiv-
ing 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 alterna-
tive relief by obtaining a certificate of identity from a diplo-
matic 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 cer-
tificates of identity entry into the United States. Thus, were
Rivera to obtain a certificate of identity and then present him-
self 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
                      RIVERA v. ASHCROFT                    203
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 pro-
ceeding could not re-evaluate 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.

   [9] Rivera is no model citizen. By his own account, he pro-
cured 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, 

, 92 (1958) (plurality
opinion), “[c]itizenship is not a license that expires upon mis-
behavior.” We reverse the District Court’s denial of Rivera’s
petition for habeas corpus and remand for further proceed-
ings.

  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.



CALLAHAN, Circuit Judge, dissenting:

  My colleagues, in a rush to correct what they perceive as
an injustice, implicitly decide what has yet to be determined
— Rivera’s citizenship — and, reasoning backward from that
determination, create jurisdiction in the district court where
none had previously existed. I dissent because their approach
conflicts with our prior opinions and is not sound.

   Whatever the shortcomings of the Immigration and Natu-
ralization Service (“INS”) and the Immigration Judge (“IJ”),
204                       RIVERA v. ASHCROFT
Rivera’s predicament is of his own making. Rivera, by his
own admissions, at the age of eighteen decided to develop an
alias. He purchased a Mexican birth certificate and used that
to apply for a Washington State driver’s license and identifi-
cation card. When he was arrested in January 1998, by a Bor-
der Patrol agent, rather than face jail or imprisonment due to
his outstanding warrants, he presented himself as a Mexican
citizen and accepted deportation to Mexico. When he was
again arrested in the United States in December 2000, Rivera
changed his tune and told the Border Patrol agents that he was
a United States citizen.

   The government, understandably leery of his representa-
tions, commenced removal proceedings against Rivera. The IJ
conducted an evidentiary hearing and determined that Rivera
had not rebutted the evidence that he was a native and citizen
of Mexico and had not provided sufficient evidence that he
was a United States citizen.

   I agree with my colleagues that the IJ’s conduct at the hear-
ings and her approach leave much to be desired. Nonetheless,
the IJ’s decision was a decision on the merits of Rivera’s
claim of citizenship. Moreover, Rivera allowed the IJ’s deci-
sion to become final, and that decision is not before this court.
It became final because Rivera, although having initially
determined to appeal the IJ’s decision, a week later waived
his appeal. As a result of the waiver of his appeal, Rivera was
deported to Mexico.1

  Although Rivera was apparently deported to Mexico in
February 2001, he did not file his petition for a writ of habeas
corpus in the district court until March 2003.
  1
   Rivera preferred to be deported to Mexico in 1998, rather than face
possible incarceration due to his outstanding warrants. Similarly, in 2001,
he preferred deportation to Mexico to the possibility of being in INS cus-
tody in this country while his appeal was pending.
                       RIVERA v. ASHCROFT                     205
   The majority, in its efforts to relieve Rivera of the conse-
quences of waiving his appeal and thereby consenting to
deportation, disregards Taniguchi v. Schultz, 

(9th Cir. 2002), and Miranda v. Reno, 

(9th Cir.
2001), and creates an improper and unworkable basis for
jurisdiction in the district court.

   In Taniguchi, the alien, like Rivera, did not file an appeal
from the IJ’s initial decision that she was removable. Instead
she filed a motion to reopen with the IJ. 

. The IJ denied the motion as untimely, the Board of
Immigration Appeals (“BIA”) denied her appeal holding that
the motion was untimely, and Taniguchi filed a petition for
review with this court. 

filed a peti-
tion for writ of habeas corpus in the district court alleging that
she was a United States citizen. 

court dis-
missed the citizenship claim for lack of jurisdiction as such
claims must be brought in the court of appeals. 

to this court.

   We considered the petition for review and appeal together.
We dismissed the petition for review explaining that
“Taniguchi’s claim of citizenship fails because she has not
exhausted her administrative remedies as required by statute.”

We then affirmed the district court’s dismissal for
lack of jurisdiction explaining: “[i]f an alien in a removal pro-
ceeding is ordered removed, but contends that she is a United
States citizen, [8 U.S.C.] § 1252(b)(5) is the exclusive statu-
tory method of determining the claim of citizenship, and it is
brought as a petition for review of a final order of removal.”

Thus, we affirmed the district court’s dismissal for
lack of jurisdiction, even though we had already determined
that Taniguchi could not seek relief under § 1252(b)(5)
because she had failed to appeal the IJ’s initial decision.

   The majority attempts to distinguish Taniguchi on the
ground that Taniguchi’s claim to citizenship was “patently
frivolous,” but this will not do. A district court must deter-
206                    RIVERA v. ASHCROFT
mine its jurisdiction on the basis of the allegations in the com-
plaint. If we hold that a district court has jurisdiction over
non-frivolous claims of citizenship, we are in essence requir-
ing that district courts entertain all petitions until such time as
the courts can determine whether they are factually frivolous.
In other words, district courts will have to entertain the cases
until such time as they have developed records which are suf-
ficient to allow the courts to rule on the merits of the petition-
ers’ allegations.

   I agree with the majority that United States citizenship
should not be easily shed and that a citizen keeps it “unless
he voluntarily relinquishes it.” Afroyim v. Rusk, 

,
262 (1967). I part company with the majority in that I find in
this record sufficient indicia of voluntary relinquishment to
justify Rivera’s current predicament. Even accepting Rivera’s
presentation as true, he chose to adopt an alias to avoid his
warrants, he chose to represent himself to the government as
a Mexican citizen, he chose to be removed to Mexico rather
than face his warrants, and he chose to waive his appeal from
the IJ’s decision and again accept removal to Mexico. Rea-
sonable minds may find that this constitutes a voluntary relin-
quishment. In any event, Rivera is not entitled to any greater,
or lesser, rights than any other person who petitions a district
court claiming to be a United States citizen.

   Even if the district court were not compelled to dismiss
Rivera’s petition under Taniguchi, it nonetheless properly dis-
missed the petition pursuant to our decision in Miranda. An
IJ there found that Miranda was an aggravated felon and
ordered him removed. 

. Miranda
waived his right to appeal to the BIA and was removed to
Mexico. 

sought review in the district court, which
held it lacked subject matter jurisdiction. 

On
appeal, we held that although the district court had general
jurisdiction to consider a habeas petition challenging a final
order of removal, Miranda’s petition had to be dismissed. We
stated: “[b]ut Miranda cannot avail himself of habeas corpus
                      RIVERA v. ASHCROFT                     207
jurisdiction because he has already been removed and there-
fore is no longer ‘in custody.’ See 28 U.S.C. § 2241; see also
Williamson v. Gregoire, 

, 1182 (9th Cir. 1998)
(‘[T]he “in custody” requirement is jurisdictional.’).”

. The district court had no jurisdic-
tion over Rivera because he was not in the Western District
of Washington when the habeas petition was filed. In fact, he
had not been in that district for over two years at the time the
petition was filed.

   The majority’s attempt to circumvent our holding in
Miranda by arguing that Rivera’s case presents an “extreme
circumstance,” citing Singh v. Waters, 

(9th Cir.
1996), converts a checkpoint into a freeway. Singh was
removed from the country after the immigration judge had
granted a stay of deportation. 

We determined that
he had been unlawfully removed because (1) “the Service
proceeded with his deportation after a stay of deportation had
been issued by the immigration judge,” and (2) “by having the
file of Singh and failing to inform his counsel . . . that it had
the file prior to the handcuffing and arrest on December 2,
1993, the Service effectively scuttled the right to counsel
guaranteed to Singh by statute.” 

We concluded:

    If the alien was kidnapped out of the country, he
    would not have departed . . . . Neither has he
    departed here when he was removed in violation of
    the immigration judge’s order and after interference
    with his right to counsel. For the same reasons, he is
    not to be charged with having failed to exhaust his
    administrative remedies when the Service by physi-
    cally removing him made the full reopening of his
    case impossible. Singh does not fall under [8 U.S.C.]
    § 1105a(c) but under § 1105a(a)(10): he is an “alien
    held in custody pursuant to an order of deportation.”

(citations omitted).
208                      RIVERA v. ASHCROFT
  A moment’s reflection reveals that Rivera does not present
an extreme circumstance as defined by Singh. There was no
order staying Rivera’s removal, or even any pending proceed-
ing in which such an order might have been sought. Rather,
he had waived his appeal to the BIA and requested removal
to Mexico “as soon as possible” (as he had previously in
1998). Accordingly, the government agents would have been
derelict in their duties if they had not promptly removed
Rivera.

   The majority, however, opines that Rivera’s acquiescence
in his removal is of no moment because it “was not made
knowingly or voluntarily.” With all due respect, there is little
before us to support this “finding.” It does not appear that
Rivera ever submitted an affidavit to the district court. Rather,
his counsel argued that the IJ did not adequately advise Rivera
of his right to appeal. But Rivera did not waive his right to
appeal before the IJ. When he left the IJ he still had his right
to appeal. Six days later he chose to abandon that right. There
is nothing in the record from Rivera indicating why he aban-
doned his appeal.

   Ultimately, the majority’s reasoning falls back upon its
assumption that Rivera is a citizen. As previously noted, how-
ever, the district court’s jurisdiction cannot turn on the under-
lying merits of an allegation of citizenship. Otherwise, any
person who was removed from the United States (and remains
outside the United States) could invoke a district court’s juris-
diction, particularly if the individual did not have counsel at
the time of removal,2 simply by alleging that he or she is a
United States citizen.
  2
    The majority stresses that Rivera did not have counsel, but does not
point to anything in the record that suggests that Rivera was denied coun-
sel or was not aware that he could have counsel. The fact that he made an
arguably poor decision in abandoning his appeal does not establish that
either that decision or his decision not to employ counsel was not freely
made. Similarly, the possibility that Rivera is a United States citizen is
                          RIVERA v. ASHCROFT                           209
   Although Rivera may be a United States citizen, this court
does not have the jurisdiction to so decide on this appeal.
Rivera, for not the first time, allowed himself to be removed
to Mexico. His removal does not, as the majority claims, ren-
der Rivera stateless. It does, however, require that he resort to
other remedies.3 Pursuant to our opinion in Miranda, Rivera
should not be allowed to invoke the district court’s jurisdic-
tion by filing a petition for writ of habeas corpus in a district
court some two years after his removal to Mexico. I would
affirm the district court’s dismissal of Rivera’s petition for
lack of jurisdiction.




not, in itself, a basis for challenging his decisions. Hundreds of thousands
of people go through immigration processes every year without counsel.
There is no basis in fact for presuming that un-counseled immigration
decisions should be open to judicial review (when counseled decisions are
not). Such a presumption would seriously undermine the country’s immi-
gration policies.
   3
     For example, 8 U.S.C. § 1503(b) sets forth a procedure for a person
outside the United States, who claims to be a United States citizen, to
obtain a certificate of identity from a United States diplomatic or consular
officer.