LEAVY, Circuit Judge:

We are called upon to determine whether subsections (a), (b)(1) and (b)(2) of 8 U.S.C. § 1326 constitute separate crimes or merely sentence enhancement provisions for the underlying crime of illegal reentry following deportation. We hold that the three subsections identify different crimes, the elements of which must be proven at trial and not simply at sentencing.

FACTS AND PRIOR PROCEEDINGS

Jose Gonzalez-Medina (“Gonzalez”), Oscar Jaquez-Velasquez (“Jaquez”), and Ricardo Reyes-Carrillo (“Reyes”) were separately charged under 8 U.S.C. § 1326 with illegally reentering the United States following deportation as convicted felons. During the course of their separate trials, the government put on evidence showing that each defendant was an illegal alien who had unlawfully reentered the United States after having been previously deported, but failed to offer any evidence that the defendants had prior felony convictions. Following instructions from the court *572 which made no mention of the allegations of defendants’ criminal records, the juries in each case convicted the defendants of illegally reentering the United States following deportation.

At their respective sentencings, the defendants argued that the government’s failure to prove their prior felony convictions precluded the court from sentencing them to terms greater than two years, i.e., the maximum provided for a conviction of illegal reentry following deportation under 8 U.S.C. § 1326(a). The government countered by arguing that (1) the defendants had each stipulated before trial to the government’s contention that it did not have to prove their prior felony convictions because the existence of a criminal record was merely a sentence enhancement provision and not a necessary element of the offense charged, and (2) any resultant error was invited error caused by the defendants themselves. The district courts rejected the defendants’ arguments and sentenced them to prison terms ranging from twenty-seven to forty-eight months each, all to be followed by three years of supervised release. The defendants have timely appealed.

ANALYSIS

In these consolidated appeals the three defendants raise a single issue, viz., whether the existence of a felony conviction is a sentence enhancement provision under 8 U.S.C. § 1326 or a necessary element of an offense charged under subsections (b)(1) and (b)(2) of section 1326. For the reasons set forth below, we conclude that the existence of a prior felony conviction is a necessary element of an offense under 8 U.S.C. § 1326(b) and that the government’s failure to prove this element at each of the defendants’ trials requires us to vacate their sentences and remand for re-sentencing.

Section 1326 of Title 8 reads, in relevant part:

(a) [A]ny alien who ... has been arrested and deported ... and thereafter ... enters ... or is at any time found in[ ] the United States ... [without permission of] the Attorney General ... shall be fined ... or imprisoned not more than 2 years, or both.

(b) Notwithstanding subsection (a) of this section, in the case of any alien described in such subsection—

(1) whose deportation was subsequent to a conviction for commission of a felony (other than an aggravated felony), such alien shall be fined ... [or] imprisoned not more than 5 years, or both; or

(2) whose deportation was subsequent to a conviction for commission of an aggravated felony, such alien shall be fined ... [or] imprisoned not more than 15 years, or both.

In United States v. Arias-Granados, 941 F.2d 996 (9th Cir.1991), we held that the defendants, who had been charged with unlawful reentry following deportation for felony convictions under 8 U.S.C. § 1326(b)(1) but had pleaded guilty to simple reentry following deportation under section 1326(a), could still have their base offense levels enhanced under U.S.S.G. § 2L1.2(b)(l) 1 by virtue of their prior felony convictions. 941 F.2d at 998-99. In reaching this conclusion we noted, however, that (1) no matter how much a defendant’s base offense level might be raised under the Sentencing Guidelines, a conviction under 8 U.S.C. § 1326(a) would limit any prison sentence imposed thereunder to a maximum of two years; and (2) sections 1326(a) and 1326(b)(1) identify two separate and distinct crimes. Id. at 998-99.

Because sections 1326(a) and 1326(b)(1) (and, a fortiori, 1326(b)(2)) constitute separate crimes — and not merely a single offense with different sentencing criteria— the government was obligated to put on evidence of the defendants’ prior felony convictions if it intended to prosecute them under section 1326(b) instead of the lesser included offense of section 1326(a). Cf. *573 Arias-Granados, 941 F.2d at 999 (referring to sections 1326(b)(1) and 1326(a), respectively, as “the greater crime” and the “crime with a lesser maximum sentence”). The government not only elected not to put on any such evidence, but acquiesced in a jury instruction that only listed the three elements of section 1326(a) rather than the four elements of section 1326(b).

We reject the government’s contention that defense counsel for both Gonzalez and Jaquez concurred in the prosecution’s interpretation of section 1326 and “stipulated” that the government did not have to put on evidence of the defendants’ prior felony convictions. Defense counsel stated only that he did not want the government to put on any such evidence, not that he agreed with an interpretation of section 1326 that would obviate the need for proof of prior felony convictions as an element of section 1326(b). No such “stipulation” appears in the Reyes’ record.

We also reject the government’s contention that the defendants waived their right to challenge their convictions by having proposed the jury instruction in question. The defendants neither attack the instruction as misstating the law regarding section 1326(a), nor contend that they are not guilty of violating that provision. Rather, they argue only that they cannot lawfully have been convicted of violating section 1326(b) when the proof at their respective trials and the instructions given were limited to section 1326(a). Largely for this reason — and ignoring the fact that the government not only did not object to the instruction but apparently submitted a similar instruction in all three cases — we also reject the government’s argument on invited error. Cf. United States v. Schaff, 948 F.2d 501, 506 (9th Cir.1991).

The juries only heard evidence regarding the defendants’ alleged violations of 8 U.S.C. § 1326(a), and were instructed only under section 1326(a). Accordingly, the defendants can only have been convicted of having violated section 1326(a). Because each of the sentences imposed exceeds the lawful maximum of twenty-four months under 8 U.S.C. § 1326(a), see Arias-Granados, 941 F.2d at 998, we must vacate the sentences imposed and remand for resen-tencing.

VACATED and REMANDED.

Notes

. That provision reads in its entirety:

If the defendant previously was deported after a conviction for a felony, other than a felony involving violation of the immigration laws, increase [his base offense level] by 4 levels.