Heriberto Bahena-Cardenas appeals from the denial of his pretrial motion to dismiss a three count indictment ^[1] charging him with violations of 8 U.S.C. § 1326(b)(1) (being a deported alien found in the United States) and 18 U.S.C. § 911 (false claims as to United States citizenship). He renewed the motion as a motion for acquittal under Fed. R.Crim.P. 29 both at the end of the government’s case-in-chief and at the close of all the evidence. The motion was denied and Bahe-na-Cardenas also appeals from that denial. We have jurisdiction over this timely appeal.

FACTUAL AND PROCEDURAL BACKGROUND

In 1987 the Immigration and Naturalization Service (“INS”) began deportation proceedings against Bahena-Cardenas based upon his 1986 conviction for conspiracy to possess and to distribute heroin. In 1990, an immigration judge found him to be a citizen of Mexico and deportable. Bahena-Carde-nas appealed that decision to the Board of Immigration Appeals (“BIA”), and thus under the law, his deportation was stayed. In October of 1993 while his appeal was pending, an employee of the INS erroneously noted on his file that the BIA had affirmed the appeal causing a warrant of deportation to be prepared and put in his A-file (immigration file). On approximately May 24, 1994 Bahena-Cardenas left San Diego for Mexico City on a Continental Airlines flight. He attempted to return to the United States by landing at San Diego airport on June 3, 1994. Upon arrival, Bahena-Cardenas was arrested at the San Diego airport and on June 7, 1994 he was charged by complaint with violations of 8 U.S.C. § 1326 and § 1326. An indictment was returned on June 17, 1994.

On August 8, 1994 the district court heard arguments on defendant’s motion to dismiss Counts 1 and 3 of the indictment. ^[2] The district court denied Bahena-Cardenas’ motion to dismiss Count 1. The case went to trial and the defendant, after the government’s case in chief, made his motion pursuant to Fed.R.Crim.P. 29 and renewed it after the close of all the evidence. He was convicted on both counts of the indictment and judgment was entered on November 28, 1994. On September 20, 1994, the BIA issued an opinion finding that Bahena-Carde-nas had waived his appeal when he “self-deported” pursuant to 8 U.S.C. § 1101(g) (“any alien ordered deported [whether before or after the enactment of this chapter] who has left the United States, shall be considered to have been deported in pursuance of law, irrespective of the source from which the expenses of his transportation were defrayed or of the place to which he deported.”).

STANDARD OF REVIEW

This court reviews de novo the district court’s denial of a pretrial motion to dismiss based on its interpretation of a federal statute. United States v. Riggins, 40 F.3d 1066, 1057 (9th Cir.1994). This court also reviews de novo a Rule 29 motion for acquittal: however, the test used is the same as that used when the challenge is to the sufficiency of the evidence. “‘[T]he relevant question is whether, after viewing the evi[*1073] dence in the light most favorable to the prosecution, any rational trier of fact could have found the essential elements of the crime beyond a reasonable doubt.’ ” Riggins, 40 F.3d at 1057, citing, Jackson v. Virginia, 448 U.S. 307, 319, 99 S.Ct. 2781, 2789, 61 L.Ed.2d 560 (1979) (emphasis in original).

DISCUSSION

Section 1326 imposes penalties on aliens who have been previously arrested and deported. The parties disagree as to the definition of the term “arrested” found in § 1326(a)(1) of the statute. ^[3] Bahena-Carde-nas argues that he was never “arrested” under the Statute prior to his self-deportation; therefore, the government cannot and did not prove every essential element of the crime beyond a reasonable doubt. He argues that the warrant of deportation was erroneously issued, ^[4] he was never served with the warrant, did not have notice of the warrant and, thus, he was never arrested prior to his unintentional self-deportation. The government argues that the mere issuance of the warrant is itself an “arrest” under the statute.

We have held that “before criminal sanctions can be imposed for re-entry after arrest and deportation, it must be shown that the INS followed 8 C.F.R. § 243.1 and issued a Warrant of Deportation.” United States v. Farias-Arroyo, 528 F.2d 904, 904-5 (9th Cir.1975) (quoting United States v. Wong Kim Bo, 472 F.2d 720, 723 (5th Cir.1972) (Wong Kim Bo II)). Farias-Arroyo had notice of the warrant, however. We are not aware of any case holding that an alien who was not served with the warrant was “arrested” under the statute. See, e.g., United States v. Quezada, 754 F.2d 1190, 1192 (5th Cir.1985) (“[A]n ‘arrest’ under the statute is accomplished by service on the alien of the warrant of deportation ... ”) (emphasis added); United States v. Hernandez, 693 F.2d 996, 998 (10th Cir.1983) (noting that “the signature of the defendant appears on the reversé side of each warrant”).

The government argues that it was unnecessary to serve the warrant on Bahena-Cardenas because he already knew the United States wanted him out of the country. The government’s argument proves too much. Any alien who has already been deported knows, or should know, that the United States does not want him in the country. The government’s argument would eliminate the arrest element altogether.

The government also contends that unless the Court affirms Bahena-Cardenas’ conviction, any self-deported alien will be free to exit and re-enter the United States without consequence. We disagree. Bahena-Carde-nas lost his right to appeal when he voluntarily “self-deported” by leaving the country; even Bahena-Cardenas concedes that he had no legal right to re-enter the United States. The government could have arrested Bahe-na-Cardenas immediately when he returned, and deported him in short order. If Bahe-na-Cardenas then attempted to re-enter the[*1074] country again, the government could have prosecuted him under § 1326. The government simply skipped these steps.

We agree with Fifth Circuit and hold that the term “arrested” in 8 U.S.C. § 1326 requires that a warrant of deportation be served on the alien. Until Congress amends the law, we will presume that “Congress affirmatively intended that aliens be afforded all notice reasonably possible relating to their status.” United States v. Wong Kim Bo, 466 F.2d 1298, 1304 (5th Cir.1972) (Wong Kim Bo I). Service of the warrant constitutes notice. Without notice, there can be no arrest, and no restraint on liberty that an arrest connotes. Wong Kim Bo I, 466 F.2d at 1305.

REVERSED.