OPINION

Gil Leon-Paz appeals his conviction and sentence for reentry after having been deported. 8 U.S.C. § 1326 (a). He asserts that he was denied due process at his deportation hearing, and, as a result, his conviction cannot stand. We vacate and remand.

BACKGROUND

Leon, who is a native and citizen of Mexico, obtained temporary residence status as a special agricultural worker in 1988, and became a lawful permanent resident in December of 1990. Thereafter, he committed a number of crimes. The last resulted in a burglary conviction on October 12, 1995, at which time he pled guilty and was sentenced to four years in state prison.

On October 10, 1997, the Immigration and Naturalization Service initiated removal proceedings against Leon by serving him with a Notice to Appear. That notice alleged that he was deportable because of his first degree burglary conviction on October 12, 1995, which constituted an aggravated felony. At his removal hearing, Leon acknowledged his conviction and the Immigration Judge informed him that he was not eligible for any form of relief because his aggravated felony conviction barred relief from removal. The IJ then ordered Leon removed from the United States, and Leon declined to appeal the IJ’s decision. He was removed to Mexico on November 24,1997.

Undaunted, Leon came back within a few days and was finally caught, had his 1997 removal order reinstated, and was removed again in December of 1999. He returned, and was removed again in January 2001, but was back on February 7, 2001, when he was arrested and, finally, prosecuted for his illegal reentry.

Ultimately, Leon filed a motion to dismiss the indictment on the basis that the original removal hearing in 1997, upon which all of his removals were based, was constitutionally defective because he was denied his right to judicial review. Therefore, he argued, the results of that hearing could not be used to support his prosecution for reentry. See United States v. Mendoza-Lopez, 481 U.S. 828, 837-39 , 107 S.Ct. 2148, 2155 , 95 L.Ed.2d 772 (1987). The district court denied the motion.

Leon then negotiated and entered into a conditional plea agreement in which he admitted guilt of the charge, but reserved the right to appeal the denial of his motion to dismiss. The district court accepted the plea and sentenced him to a total of thirty months imprisonment plus three years of supervised release and a special assessment of $100. This appeal followed.

JURISDICTION AND STANDARD OF REVIEW

The district court had jurisdiction pursuant to 18 U.S.C. § 3231 . We have jurisdiction pursuant to 28 U.S.C. § 1291 .

We review the denial of the motion to dismiss an 8 U.S.C. § 1326 indictment de novo, when the motion to dismiss is based upon an alleged due process defect in the underlying deportation proceeding. United States v. Muro-Inclan, 249 F.3d 1180, 1182 (9th Cir.2001).

DISCUSSION

In this criminal proceeding, Leon seeks to collaterally attack the removal order upon which his prosecution is based. That he cannot do if he validly waived his right to appeal the removal order. If he did, he will have failed to exhaust his administrative remedies and, also, will not have been deprived of his right to judicial review. See 8 U.S.C. § 1826 (d); United States v. Arrieta, 224 F.3d 1076, 1079 (9th Cir.2000). He did waive his right to appeal after the IJ told him that he “was not eligible for relief’ from removal. But the waiver cannot have been valid if “ ‘the record contains an inference’ ” that he was eligible for relief, but the IJ misadvised him to the contrary.

If the IJ so erred, Leon may well be entitled to relief because “[i]n a criminal prosecution under § 1326, the Due Process Clause of the Fifth Amendment requires a meaningful opportunity for judicial review of the underlying deportation. If the defendant’s deportation proceedings fail to provide this opportunity, the validity of the deportation may be collaterally attacked in the criminal proceeding.” United States v. Zarate-Martinez, 133 F.3d 1194, 1197 (9th Cir.1998) (internal citation omitted). In fact, that defect in the proceedings would demonstrate that Leon was “ ‘deprived of judicial review in violation of due process.’ ” Id. (citation omitted). It would then remain for him to show that he suffered prejudice as a result. Id.

We must, therefore, ask whether the IJ’s advice was correct. As we will show, it was not. When Leon pled guilty to first degree burglary in 1995 and received a four-year-prison sentence, his crime was not an aggravated felony for deportation purposes. See 8 U.S.C. § 1101 (a)(43)(G) (1995); 8 U.S.C. § 1251 (a)(2)(A)(iii) (1995). Therefore, at that time he was not eligible for relief from deportation because he was not deporta-ble for that crime. Cf. 8 U.S.C. § 1182 (c) (1995) (hereafter § 212(c)). Had his burglary been dubbed an aggravated felony, he would have been eligible for a § 212(c) waiver because he was not going to serve at least five years in prison for the offense. See id.

Leon could breathe easily for he had double protection, but then came the peri-peteia which led to his 1997 deportation. See Antiterrorism and Effective Death Penalty Act of 1996, Pub.L. No. 104-132, 110 Stat. 1214 (AEDPA); Illegal Immigration Reform and Immigrant Responsibility Act, Pub.L. No. 104-208, 110 Stat. 3009-546 (IIRIRA). The first blow came with § 440(d) of the AEDPA, which provided that § 212(c) relief was no longer available for aggravated felons, regardless of the length of their sentences. That did not really hurt Leon because his offense, with its four-year sentence, was still not defined as an aggravated felony. The next blow did hurt him. Section 321 of IIRIRA dubbed Leon’s burglary offense an aggravated felony by changing the definition from one where the imposed term of imprisonment was at least five years to one where the term of imprisonment was at least one year.

If that were all, Leon’s case would be hopeless because the statutes as then written made him an aggravated felon for whom relief was not available. But that, as it turns out, was not all; and the something more is what demonstrates the IJ’s error.

That something more is the Supreme Court’s determination that for people who pled guilty when § 212(c) relief was in full bloom, the amending and repealing statutes did not retroactively take away that provision. See INS v. St. Cyr, 533 U.S. 289 , 121 S.Ct. 2271 , 150 L.Ed.2d 347 (2001). In St. Cyr , the alien had pled guilty to an offense which made him de-portable, but for which § 212(c) relief was available. By the time removal proceedings were started against him, however, the statutes no longer provided for relief.

The Court was satisfied that “depriving removable aliens of consideration for § 212(c) relief produces an impermissible retroactive effect for aliens who, like respondent, were convicted pursuant to a plea agreement at a time when their plea would not have rendered them ineligible for § 212(c) relief.” Id. at 320, 121 S.Ct. at 2290 . It went on to say:

Id. at 321-22, 121 S.Ct. at 2291 (internal quotation marks and citations omitted). That same reasoning applies here.

While it is true that in 1995 Leon did not actually plead to what was then an aggravated felony, whereas St. Cyr had done so, it is also true that Leon had two bulwarks to protect himself against attacks on his residence in this country. The first was the fact that he had pled to a crime that was below the aggravated felony threshold, and the second was § 212(c) itself in case the definition of aggravated felony changed as it often had and has. The statutory changes could have pulled both of his bulwarks down. Congress was puissant enough to do so if it wished, but as St. Cyr teaches, it did not apply its full strength to § 212(c). That section remained available to protect him because, unlike § 321 of IIRIRA, the provision which removed § 212(c) relief was not made fully retroactive.

In reaching this conclusion, we are certainly aware of our decision in United States v. Velasco-Medina, 305 F.3d 839 (9th Cir.2002), upon which the. INS relies. But we find that case distinguishable. In Velasco-Medina the alien, like Leon, pled to an offense that was not an aggravated felony at the time and, therefore, § 212(c) was not then necessary or applicable. Id. at 849. But in that alien’s situation, § 212(c) could not have been one of his bulwarks. By the time he pled guilty in 1996, if later charges made him an aggravated felon, § 212(c) relief could not be in play. It had already been eliminated by the AEDPA for any aggravated felon. We were acutely aware of that and were led to observe: “Velasco-Medina would have realized that if his conviction were recharac-terized as an aggravated felony (as, in fact, it was by IIRIRA), he would have, under AEDPA, been ineligible for discretionary relief under § 212(c).” Id. at 850. We continued: “Here, AEDPA provided Ve-lasco Medina with fair notice that discretionary relief under § 212(c) would be un available in the event his conviction was reclassified as an aggravated felony.” Id. That is precisely what Leon did not know and did not have fair notice of. Moreover, while it was fair to say that Velasco “could not have developed the sort of settled expectations” that may have motivated St. Cyr, that is not true of Leon. He could rely on the fact that he had a source of protection should his crime be declared an aggravated felony in the future. He, like St. Cyr, was entitled to the continued protection of § 212(c), and the IJ erred when he told Leon that no relief was available. There was, therefore, a due process violation, and the district court erred when it held to the contrary.

CONCLUSION

Leon’s case is a congener of St. Cyr’s, and like St. Cyr he was entitled to be considered for § 212(c) relief. When he was given advice to the contrary and, thus, deprived of that possibility and of an appeal, his due process rights were violated.

That alone does not mean that Leon is entitled to dismissal of the indictment. He must still show prejudice. See Arrieta, 224 F.3d at 1079-80 ; United States v. Proa-Tovar, 975 F.2d 592, 595 (9th Cir. 1992). But the district court never reached that issue, and it should do so in the first instance. See United States v. Lopez-Vasquez, 1 F.3d 751, 755-56 (9th Cir.1993). We, therefore, vacate Leon’s conviction and sentence, and remand the case to the district court so that it can consider whether Leon was prejudiced by the deprivation of his due process rights in his 1997 removal proceeding. If he was not prejudiced, the district court may reinstate the conviction and sentence. If he was prejudiced, the district court must dismiss the indictment.

VACATED and REMANDED.

. See Muro-Inclan, 249 F.3d at 1182 (citation omitted). . Leon asserts that he was, indeed, deportable because he had committed many other crimes and could have been deported pursuant to 8 U.S.C. § 125 l(a)(2)(A)(ii) (1995). Suffice it to say that no attempt has ever been made to deport him on that basis, and the information was not before the IJ. See Moran-Enriquez v. INS, 884 F.2d 420, 422-23 (9th Cir.1989); Bu Roe v. INS, 771 F.2d 1328, 1334 (9th Cir.1985). . By that time, § 212(c) had been replaced by 8 U.S.C. § 1229b(a), which, like the amended § 212(c), gave no help whatsoever to aggravated felons. . Id. at 849.