BETTY B. FLETCHER,
Circuit Judge.
Osama Musa Alferahin appeals his conviction under 18 U.S.C. § 1425(a) for knowingly procuring naturalization “contrary to law.” The basis for this conviction was Alferahin’s failure to disclose, on an application for permanent resident status, that he had been previously married. On appeal, Alferahin contends that the district court erred by failing to instruct the jury that 18 U.S.C. § 1425(a) contains a requirement of “materiality.” Alferahin further contends that his attorney’s failure to obtain an instruction on the issue of materiality constituted a denial of his right to effective assistance of counsel under the Sixth Amendment. We reverse his conviction and remand for a new trial.
I.
Osama Musa Alferahin was born in Kuwait as a citizen of Jordan. He has married twice. He married his first wife— Alicia Jaremo Y Pradeñas, a citizen of Spain — on February 27, 1995. According to Alferahin, he divorced her in a religious ceremony at the Islamic Cultural Center in Madrid, Spain, on September 1, 1997. That divorce, however, was not officially recorded in the Spanish civil registry until February 16, 2000.
Alferahin married his second wife— Reem Alferahin, a naturalized citizen of the United States — on December 31, 1997, in Amman, Jordan. A little more than one month later, on February 2, 1998, he applied for permanent residence in the United States based on his status as the spouse of an American citizen. Alferahin thus married his second wife and applied for permanent residence in the United States after the religious ceremony in Spain in which he claims to have divorced his first wife, but before the Spanish civil registry had recorded that divorce officially.
As part of Alferahiris application for permanent residence, his second wife signed and submitted a petition known as Form 1-130. Because Form 1-130 involves an application for permanent residence based on an alien’s marriage to an American citizen, this form requires the petitioner to disclose the existence of any and all [1152]*1152previous marriages involving either the United States citizen or the alien-spouse, as well as the date of the dissolution of those marriages. Alferahin, who testified that he prepared Form 1-130 himself on behalf of his wife, provided inaccurate information on this form. In response to questions about the existence and dissolution of previous marriages, Alferahin responded “N/A,” implying that the questions were not applicable to him.
On the basis of the information submitted on Form 1-130, Alferahin obtained status as a permanent resident. Two years later, in May of 2002, Alferahin became a naturalized citizen. More than one year after obtaining citizenship — and more than five years after he submitted his application for permanent residence — -Alferahin was arrested and charged with the crime of knowingly procuring naturalization contrary to law. See 18 U.S.C. § 1425(a)(pun-ishing those who “knowingly procure! ] or attempt! ] to procure, contrary to law, the naturalization of any person, or documentary or other evidence of naturalization or of citizenship”).
At trial, the government contended that Alferahin deliberately withheld information about his first marriage from his application. According to the government, Alferahin had explained to an INS investigator that he omitted the information because he “didn’t want to complicate the process.” The government further emphasized that the omitted information was pertinent to Alferahin’s application because his petition for permanent residence depended on the validity of his second marriage to an American citizen. The disclosure of truthful information, the government contended, would have led immigration officials to investigate the dissolution of Alferahin’s first marriage and to inquire into the validity of his second.
In opposition to the government’s position, Alferahin provided a culturally based explanation for the inaccuracies. He explained that, in Moslem culture, a man may have multiple wives and need not disclose his marital status; he claimed that due to this cultural background, he had responded “not applicable” based on his belief that the questions literally did not apply to him. The defense also downplayed the significance of the omitted information. For instance, Alferahin’s wife testified that they considered information about his marital status “just not important.” In addition, defense counsel cross-examined the government’s witnesses on the likely consequences of a complete disclosure by Alferahin, suggesting that the INS would have processed his application for permanent residence in exactly the same fashion if Alferahin had revealed the existence of his first marriage.
At the conclusion of the trial, the district court noted that there were “no stock instructions on this particular crime.” Since neither side had proposed jury instructions on the elements of the charged offense, the district court drafted instructions on its own for the attorneys to review. There was no mention of the need for an instruction on materiality.
During closing arguments, however, both the prosecution and the defense called the jury’s attention to the significance of the omitted information. The prosecution argued that Alferahin had “concealed a material fact,” adding that the existence of Alferahin’s first marriage “is a material fact because we need to know if there’s some sort of marriage fraud going on.” 1 By contrast, the de[1153]*1153fense underscored the insignificance of the information, emphasizing that “we’re arguing over what is an irrelevant fact” and noting that the government’s witnesses had not testified that Alferahin’s application would have been denied even if Alferahin had properly disclosed his first marriage. Alferahin’s attorney argued: “No one is even suggesting that Osama would not have been granted citizenship if he had put Alicia’s name and their divorce dates ... on the 1-130.”
During the middle of closing arguments, the district court noted this emphasis on materiality and, sua sponte, raised the question of a materiality instruction. Pointing to the government’s argument that Alferahin’s omission had been material, the district judge noted that materiality was not one of the elements included in the jury instructions and suggested that “perhaps it should have been.” The government responded that the proposed instructions “mirror[ed] the statute.” But the government did not object to the materiality instruction, adding that “we have always put in all of our proof with respect to this case that it was material, to cover ourselves, ... because in other statutes that we were contemplating charging the defendant with, materiality was always an issue.”
When the district court asked defense counsel whether a materiality instruction was necessary, Alferahin’s attorney responded: “I don’t think it’s appropriate.” The defense noted that materiality was not part of the indictment, and he stated that, if there had been an allegation that the omitted information was material, he would have called an expert witness to discuss the meaning of materiality, adding that “now it’s sort of beyond the pale.” The district court asked: “Do you feel that the elements in the instruction are complete and accurate as far as what the government has to prove in the case?” Alferahin’s attorney replied: ‘Tes.” Satisfied that the defense considered the proposed instructions an accurate reflection of applicable law, the judge submitted the instructions to the jury unamended.
The jury convicted Alferahin, and the district court sentenced Alferahin to time served, as well as to thirty-six months of supervised release. The district court also revoked Alferahin’s United States citizenship. See 8 U.S.C. § 1451(e) (“When a person shall be convicted ... of knowingly procuring naturalization in violation of law, the court in which such conviction is had shall thereupon revoke, set aside, and declare void the final order admitting such person to citizenship, and shall declare the certificate of naturalization of such person to be canceled.”).
Alferahin argues that his conviction is invalid. We have jurisdiction to consider his appeal under 28 U.S.C. § 1291.,
II.
Alferahin makes two arguments on appeal: first, that the district court erred in failing to instruct the jury that to convict it must find beyond a' reasonable doubt that his misrepresentations were material; and second, that his attorney’s failure to procure an instruction on the issue of materiality constituted ineffective assistance of counsel under Strickland v. Washington, 466 U.S. 668, 104 S.Ct. 2052, 80 L.Ed.2d 674 (1984). We address each argument in turn.
A
Alferahin’s first contention is that the district court submitted legally erroneous jury instructions regarding the elements of the crime. Defense counsel, however, raised no objection at trial to the allegedly erroneous jury instructions. Indeed, Alferahin’s attorney not only failed [1154]*1154to object to the omission of a materiality instruction, but he explicitly rejected the judge’s suggestion that such an instruction might be appropriate. When a defendant fails to raise a legal objection at trial but raises the objection for the first time on appeal, we review only for plain error. See FED. R. CRIM. P. 52(b); CHARLES ALAN WRIGHT ET AL., FEDERAL PRACTICE & PROCEDURE § 856, at 490-514 (3d ed.2004). Therefore, we must determine not only whether the jury instructions were incorrect, but whether their submission to the jury was plainly erroneous.2
Under the plain error doctrine, a defendant must establish (1) that the proceedings below involved error, (2) that the error is plain, and (3) that the error affected the substantial rights of the aggrieved party. See United States v. Olano, 507 U.S. 725, 732-35, 113 S.Ct. 1770, 123 L.Ed.2d 508 (1993). In addition, a defendant must also show that the error “ ‘seriously affect[s] the fairness, integrity or public reputation of judicial proceedings’ ” before we will exercise our discretion pursuant to Rule 52(b) to correct the plain error. See id. at 736, 113 S.Ct. 1770(quoting United States v. Atkinson, 297 U.S. 157, 160, 56 S.Ct. 391, 80 L.Ed. 555 (1936)); see also United States v. Vences, 169 F.3d 611, 613 (9th Cir.1999).
Federal law prohibits an alien from knowingly procuring United States citizenship “contrary to law.” 18 U.S.C. § 1425(a). In United States v. Puerta, 982 F.2d 1297 (9th Cir.1992), we held that § 1425(a) contains a materiality requirement. See id. at 1305. We concluded that, in order to obtain a conviction under this section, the government must prove (1) that the false information provided by the defendant has a tendency to suggest that he was qualified for naturalization, (2) that the production of truthful information would have led to the discovery of facts relevant to the alien’s petition for naturalization, and (3) that there must be evidence sufficient to “give rise to a ‘fair [1155]*1155inference’ ” that the applicant was statutorily ineligible for naturalization. Id. at 1300-01,1303-04 (quoting Kungys v. United States, 485 U.S. 759, 783, 108 S.Ct. 1537, 99 L.Ed.2d 839 (1988) (Brennan, J., concurring)). We thus reversed the conviction of an alien who had provided false information on his application for permanent residence as to his date and place of birth, finding that there was “no evidence” from which any finder of fact could fairly infer that Puerta was actually ineligible for naturalization. Id. at 1305.
We emphasized in Puerta the uniqueness of a denaturalization proceeding. Indeed, we stressed that we were “look[ing] to the standards governing materiality in the denaturalization context as a guide to determining what is ‘contrary to law under 18 U.S.C. § 1425.” Id. at 1301 (emphasis added). As a result, in Puerta we relied on Kungys v. United States as the “leading denaturalization case.” Id.
In Kungys, the Supreme Court interpreted a statutory provision that directed United States attorneys to begin denaturalization proceedings against any naturalized citizen who procured citizenship “by concealment of a material fact or willful misrepresentation.” Kungys, 485 U.S. 759, 764, 108 S.Ct. 1537, 99-L.Ed.2d 839 (1988) (plurality opinion) (quoting 8 U.S.C. § 1451(a)). While the Kungys Court produced multiple opinions on the meaning of “materiality,” all nine Justices agreed that a material misrepresentation must have at least “a natural tendency to produce the conclusion that the applicant was qualified” for citizenship. Id. at 771-72, 108 S.Ct. 1537. Additionally, the Justices all agreed that a misrepresentation would not be material unless an honest representation “would predictably have disclosed other facts relevant to [the applicant’s] qualifications.” Id. at 774, 108 S.Ct. 1537.
In addition to these requirements, however, Justice Brennan’s controlling opinion in Kungys emphasized that “citizenship is a most precious right, and as such should never be forfeited on the basis of mere speculation or suspicion.” Id. at 783-84, 108 S.Ct. 1537 (Brennan, J., concurring) (citation omitted). Justice Brennan therefore opined that the government also had to support its assertion of materiality with “evidence sufficient to raise a fair inference that a statutorily disqualifying fact actually existed.” Id. at 783, 108 S.Ct. 1537. Thus, the Kungys decision established a more rigorous definition of materiality that is unique to the context of denaturalization proceedings.
Building on Kungys, we held in Puerta that the prohibition under 18 U.S.C. § 1425(a) on the procurement of citizenship “contrary to law” incorporated not only á requirement of materiality, but the unique definition of materiality articulated in Justice Brennan’s controlling opinion in Kungys. See Puerta, 982 F.2d at 1301, 1303-04. In doing so, we recognized “the potential anomaly in Justice Brennan’s test in Kungys, which contemplates a higher standard of materiality in immigration law than does the criminal law generally.” Id. at 1305. We concluded in Puerta — with complete awareness of potentially incongruous constructions in the criminal law — that relevant Supreme Court precedent in the context of denaturalization required us to read § 1425(a) as containing a heightened materiality requirement. Under Puerta, then, the crime charged against Alferahin includes not only a requirement of materiality, but the more substantial requirement that the government produce evidence sufficient to raise a fair inference that Alferahin was statutorily ineligible for permanent residence.
The government argues that Puerta was decided incorrectly and that § 1425(a) contains no materiality requirement. In support of this argument, the government re[1156]*1156lies on United States v. Wells, 519 U.S. 482, 117 S.Ct. 921, 137 L.Ed.2d 107 (1997), a case in which the Supreme Court held that there was no materiality requirement in a statute that criminalized “knowingly mak[ing] any false statement or report” to a federal bank. Id. at 483, 117 S.Ct. 921 (quoting 18 U.S.C. § 1014 (1994)) (alteration in original). We are unpersuaded that the Supreme Court’s decision in Wells undermines our decision in Puerta. First, Wells involved entirely different statutory language (whereas Wells construed a statute prohibiting “false statements,” Puerta involved a statute prohibiting the procurement of citizenship “contrary to law”) and pertains to an entirely different statutory context (whereas Wells involved a criminal statute, Puerta involved the unique context of denaturalization proceedings). Moreover, the Wells Court was careful to distinguish its holding from other cases involving the issue of materiality, including the Kungys decision upon which we relied in Puerta. See Wells, 519 U.S. at 491-94,117 S.Ct. 921 & n. 10 (acknowledging the continuing viability of Kungys and implicitly rejecting the broad rule that a requirement of materiality must'always be explicit in the statutory text). Given our reliance on “the standards governing materiality in the denaturalization context,” 982 F.2d at 1300-01, and our explicit recognition of potentially incongruous materiality requirements in the criminal context, we think that Wells does little to undermine either the reasoning or the holding of Puerta.3
Because we conclude that Puerta is still good law and that 18 U.S.C. § 1425(a) contains a requirement of materiality, we find that it was error for the district court to fail to instruct the jury on this element of the crime. See United States v. Mendoza, 11 F.3d 126, 128-29 (9th Cir.1993).
Having determined that the jury instructions were erroneous, we must now determine whether the error was plain. Under the Supreme Court’s decision in United States v. Olano, an error is plain when it is “clear” or “obvious” under the law. 507 U.S. at 734, 113 S.Ct. 1770.
[1157]*1157We conclude that the error contained in Alferahin’s jury instruction was indeed plain. Our decision in Puerta unambiguously established materiality as an element of the crime of knowingly procuring naturalization contrary to law under § 1425(a), and that decision was binding on the district court in this case. We thus hold that a district court’s error is plain when its jury instructions fail to incorporate an element of the crime that has been clearly established by Ninth Circuit precedent. See United States v. Perez, 116 F.3d 840, 846-47 (9th Cir.1997) (en banc) (finding plain error where a judge submitted incomplete jury instructions, despite the fact that months-old circuit court precedent “clearly and unambiguously required the submission of the ‘in relation to’ element to the jury” in a prosecution for use of a firearm in relation to drug trafficking); United States v. Gaudin, 28 F.3d 943, 951-52 (1994) (en banc) (finding plain error where a judge failed to submit a “materiality” instruction because fifteen-year-old Ninth Circuit precedent had established materiality as an element), aff'd 515 U.S. 506, 115 S.Ct. 2310, 132 L.Ed.2d 444 (1995).
Hi
We also conclude that the submission of the plainly erroneous jury instructions affected Alferahin’s substantial rights.
It is a basic tenet of due process that a criminal defendant’s conviction must rest upon a jury’s finding beyond a reasonable doubt that he is guilty of each element of the crime charged. See United States v. Gaudin, 515 U.S. 506, 511, 115 S.Ct. 2310, 132 L.Ed.2d 444 (1995) (“The Constitution gives a criminal defendant the right to demand that a jury find him guilty of all the elements of the crime with which he is charged; one of the elements in the present case is materiality; respondent therefore had a right to have the jury decide materiality.”); see also Sullivan v. Louisiana, 508 U.S. 275, 277-78, 113 S.Ct. 2078, 124 L.Ed.2d 182 (1993) (“The prosecution bears the burden of proving all elements of the offense charged, and must persuade the factfinder ‘beyond a reasonable doubt’ of the facts necessary to establish each of those elements” (citations omitted)); Carella v. California, 491 U.S. 263, 265, 109 S.Ct. 2419, 105 L.Ed.2d 218 (1989) (“The Due Process Clause of the Fourteenth Amendment denies States the power to deprive the accused of liberty unless the prosecution proves beyond a reasonable -doubt every element of the charged offense. Jury instructions relieving States of this burden violate a defendant’s due process rights.” (citing In re Winship, 397 U.S. 358, 364, 90 S.Ct. 1068, 25 L.Ed.2d 368 (1970))); Perez, 116 F.3d at 847(“Failure to submit an essential element to a jury relieves the prosecution of its obligation to prove every element beyond a reasonable doubt.” (citing Carella v. California, 491 U.S. 263, 265, 109 S.Ct. 2419, 105 L.Ed.2d 218 (1989) (per curiam) (citing In re Winship, 397 U.S. 358, 364, 90 S.Ct. 1068, 25 L.Ed.2d 368 (1970)))). Simply put, Alferahin was not convicted of procuring naturalization contrary to law, as we have defined that crime; rather, he was convicted of committing only some of the elements of that crime. A defendant’s due process rights are unquestionably implicated when his purported conviction rests on anything less than a finding of guilt as to all the elements of the crime.
We recognize, as the government points out, that the omission of an element from jury instructions does not always “affect” a defendant’s substantial rights and that the failure to submit an element to the jury is not per se prejudicial. See, e.g., Neder v. United States, 527 U.S. 1, 15, 119 S.Ct. 1827, 144 L.Ed.2d 35 (1999) (holding that “the omission of an element is an [1158]*1158error that is subject to harmless-error analysis”); United States v. Baldwin, 987 F.2d 1432, 1439 (9th Cir.1993) (holding that a defendant had failed to establish prejudice as a result of an omitted element because the defendant’s conviction on other counts was “the functional equivalent” of a finding as to the omitted element). For example, in United States v. Neder, 197 F.3d 1122 (11th Cir.1999), on remand from 527 U.S. 1, 119 S.Ct. 1827, 144 L.Ed.2d 35 (1999), the Eleventh Circuit held that the omission of a materiality instruction was harmless error. Id. at 1134. In that case, however, the government’s evidence “incontrovertibly established] that Neder’s false statements were material” to the charged crimes of tax and bank fraud, and the defendant’s attorney did not even argue to the jury or on appeal that it would be possible for a factfinder to conclude that the defendant’s false statements were immaterial. Neder, 527 U.S. at 16, 119 S.Ct. 1827. Other cases have also upheld convictions rendered on incomplete or erroneous jury instructions, but like Neder, these cases have relied on the existence of “strong and convincing evidence” that the missing element of the crime had been adequately proved by the prosecution. Perez, 116 F.3d at 848; see also United States v. Smith, 282 F.3d 758 (9th Cir.2002) (holding that the omission of an element from jury instructions was not plain error where the underlying fact supporting the element was “undisputed” based on the “uncontroverted testimony” of a government witness).
In this case, we are unpersuaded that the evidence against Alferahin was so strong or convincing that the omission of materiality from the jury instructions did not affect his substantial rights. Quite the opposite: the record contains ample support for Alferahin’s contention that he was prejudiced by the omission of the materiality requirement. Defense counsel presented evidence supporting the view that the information omitted from Form 1-130 was immaterial, including testimony by Alferahin’s wife that they considered the information about his first marriage unimportant and cross-examination of INS officials regarding what actions the agency would have taken if it had discovered the truth about Alferahin’s first marriage. Defense counsel’s effort to minimize the significance of information pertaining to Alferahin’s first marriage is also evident in his attorney’s closing statements, in which he argued that truthful disclosure would not have affected Alferahin’s application for permanent residence and emphasized that “we’re arguing over what is an irrelevant fact.”
Unquestionably, a materiality instruction would have buttressed the defense’s strategy of downplaying the importance of Alferahin’s misrepresentations. Obviously, if the district court had directed the jury to consider the materiality of Alferahin’s misrepresentations and explained the meaning of “materiality” in the context of a denaturalization proceeding, the defense would have had more traction. Indeed, the defense’s approach to the case was quixotic; without the materiality instruction, the jury properly would have disregarded Alferahin’s immateriality argument if it had followed the instructions submitted by the district court. Because Alferahin purported to contest — and, but for the omission from the jury instructions of one of the elements of the crime, might have effectively contested — the issue of materiality, we find that the incomplete jury instructions were in fact prejudicial to him.4
[1159]*1159
iv.
Because the jury instructions were erroneous, the error was plain, and the error affected Alferahin’s substantial rights, we have “authority to order the correction” of the plain error under Rule 52(b). Olano, 507 U.S. at 735, 113 S.Ct. 1770. But the language of Rule 52(b) is permissive, not mandatory, and therefore we are not “required to do so.” Id.
As the Supreme Court has instructed, “[t]he court of appeals should correct a plain forfeited error affecting substantial rights if the error ‘seriously affect[s] the fairness, integrity or public reputation of judicial proceedings.’ ” Id. at 736, 113 S.Ct. 1770 (quoting United States v. Atkinson, 297 U.S. 157, 160, 56 S.Ct. 391, 80 L.Ed. 555 (1936)). We have relied on this so-called “final, discretionary prong” of Olano and have declined to correct plain error where we concluded that the greater threat to the integrity and fairness of judicial proceedings would arise from the reversal of a conviction on flawed jury instructions rather than from affirming an imperfect verdict. See Perez, 116 F.3d at 848 (citing Johnson, 520 U.S. at 470, 117 S.Ct. 1544). Sitting en banc in Perez, for example, the Ninth Circuit declined to exercise its discretion to correct the plain error of incomplete jury instructions because the government’s “strong and convincing evidence” demonstrated that a different decision by the jury would be “extremely unlikely.” Id.; see also Johnson v. United States, 520 U.S. 461, 470, 117 S.Ct. 1544, 137 L.Ed.2d 718 (1997) (refusing to reverse plain error of an omitted materiality instruction where the evidence of materiality was “overwhelming”); United States v. Uchimura, 125 F.3d 1282, 1287 (9th Cir. 1997) (same). In conducting this final phase of plain error analysis, the Ninth Circuit has therefore instructed that “we consider all circumstances at trial including the strength of the evidence against the defendant.” Perez, 116 F.3d at 847(quoting United States v. Campbell, 42 F.3d 1199, 1204 (9th Cir.1994), cert. denied, 514 U.S. 1091, 115 S.Ct. 1814, 131 L.Ed.2d 738 (1995) (internal quotation marks omitted)).
We conclude that it is appropriate to exercise our discretion to correct the plain error embodied in the incomplete jury instructions and remand for a new trial. The government produced evidence that the information about Alferahin’s first marriage was relevant, insofar as his application for permanent residence rested on the validity of his marriage to Reem Alferahin. But that evidence fell far short of proving materiality, as we have defined that term in the context of § 1425(a). In order to obtain a conviction against Alferahin under 18 U.S.C. § 1425(a), the govern[1160]*1160ment had to provide evidence “giving rise to a ‘fair inference’ of ineligibility.” Puerto, 982 F.2d at 1304(quoting Kungys, 485 U.S. at 783, 108 S.Ct. 1537(Brennan, J., concurring)). Proof of materiality in Alferahiris case would therefore require the government to produce evidence showing that the disclosure of information about Alferahin’s first marriage would have given rise to evidence that fairly suggests the invalidity of Alferahiris second marriage. The government did not make, much less attempt, such a specific showing here. Indeed, the government’s evidence only hinted at the possibility of the invalidity of Alferahiris second marriage.5 Accordingly, we reverse Alferahiris conviction and remand the case for a new trial.
B.
Alferahiris second contention is that his attorney deprived him of his Sixth Amendment right to effective assistance of counsel when he rejected the district court’s proffer of a materiality instruction.6 Under Strickland, a defen[1161]*1161dant who complains that his attorney has provided ineffective assistance must demonstrate two things to establish a claim under the Sixth Amendment. First, the defendant must show that his attorney’s performance “fell below an objective standard of reasonableness.” Strickland, 466 U.S. at 688, 104 S.Ct. 2052. Second, the defendant must show prejudice — that is, he must demonstrate “a reasonable probability that, but for counsel’s unprofessional errors, the result of the proceeding would have been different.” Id. at 694, 104 S.Ct. 2052.
As to the first element of the Strickland inquiry, we conclude that the performance of Alferahin’s attorney fell below an objective standard of reasonableness. As far as deficient performance is concerned, our holding in United States v. Span, 75 F.3d 1383 (9th Cir.1996), is precisely on point. In that case, as in the present one, the defense attorney failed to obtain an instruction on a critical element of the charged crime and thereby abandoned one of his client’s most promising defenses. Id. at 1390. In Span, we observed: “Counsel’s errors with the jury instructions were not a strategic decision to forego one defense in favor of another. They were the result of a misunderstanding of the law.” Id. We held in Span that the attorney’s failure to procure favorable jury instructions constituted ineffective assistance of counsel. Id. at 1390-91.
As in Span, defense counsel in this case considered the erroneous jury instructions “accurate as far as what the government has to prove in the case.” Moreover, during closing arguments defense counsel indicated to the district court that he would have produced additional testimony if he had understood that the prosecutor was obliged to prove the materiality of his client’s misrepresentations. It is thus clear from the record that Alferahin’s attorney did not intend strategically to- fore-go the materiality instruction. Instead, he had -no idea that such an instruction was available to his client as a matter of right. While the government suggests that there may be unarticulated strategic reasons for the actions of defense- counsel in this case, it does not offer any such plausible explanations, and we cannot imagine any. As we stated in Span: “We have a hard time seeing what kind of strategy, save an ineffective one, would lead a lawyer to deliberately omit his client’s only defense, a defense that had' a ... likelihood of success, and a defense that he specifically stated he [1162]*1162[would have] had every intention of presenting.” Id. at 1390.
We turn, then, to the second element of the Strickland inquiry: prejudice. For the reasons set forth in our plain error analysis above, we conclude that Alferahin was prejudiced by his lawyer’s decision to decline the proffered instruction on materiality. Defense counsel produced significant evidence relating to the immateriality of the defendant’s statements — indeed, one of Alferahin’s attorney’s tactics throughout the trial was to persuade the jury that the information omitted from his application for permanent residence was not germane to his admission to the country and that the INS would have handled the application in exactly the same way even if it had known about Alferahin’s first wife. A materiality instruction would have helped defense counsel’s strategy of emphasizing the unimportance of Alferahin’s misrepresentations, and the decision by Alferahin’s attorney to refuse the materiality instruction prevented the jury from considering the very theory of the case on which the attorney was relying. Under these circumstances, the attorney’s performance was prejudicial to Alferahin, thereby satisfying the second prong of Strickland7
III.
We hold that the submission of incomplete jury instructions was plain error in this case and that Alferahin’s attorney provided constitutionally deficient assistance when he declined an offer by the judge to instruct the jury on the element of materiality. For these two independent reasons, Alferahin is entitled to a new trial. REVERSED and REMANDED.