MOORE, J., delivered the opinion of the court in which MERRITT, J., joined. BUSH, J. (pp. 326-31), delivered a separate dissenting opinion.
Hatem Ataya pleaded guilty to one count of conspiracy to commit healthcare fraud and wire fraud. His plea agreement included a waiver of his appeal rights. During his plea colloquy, Ataya acknowledged that he understood that he was waiving these rights. The district court, however, failed to comply with Federal Rule of Criminal Procedure 11(b)(1)(J), (K), (L), and (O) during the colloquy. Ataya now seeks to vacate his conviction on the grounds that his plea was unknowing due to these Rule 11 omissions, and asserts that the appellate-waiver provision in his plea agreement is unenforceable because of these same errors. For the following reasons, we hold that Ataya's appellate waiver is unenforceable, deny the government's motion to dismiss, and REVERSE his conviction. We REMAND for further proceedings consistent with this opinion.
I. BACKGROUND
In March 2016, Ataya pleaded guilty to one count of conspiracy to commit healthcare fraud and wire fraud, in violation of 18 U.S.C. § 1349. R. 145 (Plea Agreement at 1) (Page ID #979). Ataya was a doctor in Michigan who operated Hatem M. Ataya, M.D., P.C. R. 245 (Plea Hr'g Tr. at 12) (Page ID #1943). Between 2009 and 2015, Ataya would refer Medicare beneficiary patients to entities owned or controlled by one of his co-defendants, purportedly for home health and hospice services that were, at times, "neither medically necessary nor provided." Id. at 12-13 (Page ID #1943-44). These referrals enabled Ataya's co-defendant to submit false and fraudulent claims to Medicare. Id. at 13 (Page ID #1944). In exchange for his referrals, *321Ataya received kickbacks. Id. at 12 (Page ID #1943).
At Ataya's plea hearing, the district court failed to address a number of considerations that are required under Federal Rule of Criminal Procedure 11(b)(1). First, "the district court did not inform Ataya, as Rule 11 requires, that the plea agreement required him to pay restitution and a special assessment and to forfeit the proceeds of his fraud." United States v. Ataya , 869 F.3d 401, 402 (6th Cir. 2017) (citing Fed. R. Crim. P. 11(b)(1)(J), (K), and (L) ). Second, "neither the plea agreement nor the district court seems to have mentioned that Ataya, who became a naturalized citizen after the alleged frauds, might face denaturalization as a result of his conviction." Id. (citing Fed. R. Crim. P. 11(b)(1)(O) ). The district court did, however, review with Ataya the provision of his plea agreement in which he waived his right to appeal and confirmed that Ataya had no questions about the appellate waiver. R. 145 (Plea Agreement at 11, ¶ 9) (Page ID #989); R. 245 (Plea Hr'g Tr. at 14-15) (Page ID #1945-46). The waiver states, in part: "Defendant waives any right he may have to appeal his conviction on any grounds. ... This waiver shall not be construed to bar a claim by Defendant of ineffective assistance of counsel." R. 145 (Plea Agreement at 11-12, ¶ 9) (Page ID #989-90).
The district court subsequently sentenced Ataya to ninety-seven months' imprisonment, followed by three years' supervised release. R. 205 (J. at 2-3) (Page ID #1595-96). Ataya was also ordered to pay $4,119,711.29 in restitution, forfeit specific property, and pay a $100 special assessment. Id. at 5-6 (Page ID #1598-99).
Ataya appealed the judgment against him, and the government moved to dismiss on the basis of the appellate waiver. Reviewing the government's motion to dismiss, we held that "[w]hile we agree with the government that Ataya knowingly waived his appellate rights, we are not convinced that Ataya entered into the plea agreement as a whole knowingly and voluntarily." Ataya , 869 F.3d at 402. We instructed the parties to address two issues in their merits briefs: "whether the plea agreement and the district court adequately informed Ataya of his plea's consequences, in particular any possibility of denaturalization, and if not whether any omissions constitute plain error." Id. We thus left for future resolution the government's motion to dismiss. Id.
II. DISCUSSION
A. Waiver of the Right to Appeal
The government moved to dismiss this appeal on the basis of the appellate-waiver provision in Ataya's plea agreement. Gov't Mot. to Dismiss at 2. In response, Ataya argues that his waiver was not "knowing and intelligent," and thus it is unenforceable. Def. Resp. at 2.
"We will enforce an appeal waiver included in a plea agreement when the agreement is made knowingly and voluntarily." United States v. Morrison , 852 F.3d 488, 490 (6th Cir. 2017). Ataya "may challenge his waiver of appeal rights only 'on the grounds that it was not knowing and voluntary, was not taken in compliance with Fed. R. Crim. P. 11, or was the product of ineffective assistance of counsel.' " Id. (quoting United States v. Detloff , 794 F.3d 588, 592 (6th Cir. 2015) ).
We previously held that "Ataya knowingly waived his appellate rights. His plea agreement included a broad waiver provision, and the district court confirmed that Ataya understood and accepted the waiver's consequences." Ataya , 869 F.3d at 402. But, "[f]or an appellate waiver to be knowing and voluntary, the defendant ...
*322must have entered into the plea agreement as a whole knowingly and voluntarily." Id. Because "[a] defendant decides to waive the right to challenge his conviction in light of his understanding of the conviction's key consequences[,] [i]f he misunderstands any of those consequences, that undermines the knowingness of the appellate waiver." Id.
Normally, we must first determine whether a defendant's appeal is barred by an appellate-waiver provision before considering the defendant's arguments on the merits. See, e.g. , Morrison , 852 F.3d at 490. But here Ataya's argument for why his appeal is not barred by his waiver of appeal rights is the same as why his conviction should be vacated: He did not enter into the plea agreement knowingly due to the district court's Rule 11 error. Appellant Br. at 9. Because the enforceability of the appellate waiver stands or falls with the validity of the agreement, Ataya , 869 F.3d at 402, we must consider whether the plea agreement as a whole was knowing and voluntary in order to determine whether Ataya's appeal is barred by his waiver. United States v. Portillo-Cano , 192 F.3d 1246, 1250 (9th Cir. 1999) ("[The defendant] is challenging the soundness of his plea allocution under Rule 11, which goes to the heart of whether his guilty plea, including the waiver of appeal, is enforceable. Thus we must determine whether the plea was valid in order to determine if appeal is permitted."); United States v. Rollings , 751 F.3d 1183, 1189-90 (10th Cir. 2014) (collecting cases in which courts analyzed "the totality of the plea agreement-both the appellate waiver and the plea provisions-in determining whether the plea agreement was knowing and voluntary" and collapsing the analysis of whether the appellate waiver, and thus whether the circuit court could hear the appeal on its merits, into an analysis of the merits); United States v. Puentes-Hurtado , 794 F.3d 1278, 1284 (11th Cir. 2015) (same); cf. In re Acosta , 480 F.3d 421, 422 (6th Cir. 2007) ("[I]n cases where a defendant argues that his plea was not knowing or voluntary ... it would be entirely circular for the government to argue that the defendant has waived his right to an appeal or a collateral attack when the substance of his claim challenges the very validity of the waiver itself.").
B. Standard of Review
Because Ataya "let[ ] Rule 11 error[s] pass without objection in the trial court ... [he] has the burden to satisfy the plain-error rule and ... [we] may consult the whole record when considering the effect of any error on substantial rights." United States v. Vonn , 535 U.S. 55, 58-59, 122 S.Ct. 1043, 152 L.Ed.2d 90 (2002). Plain-error review "involves four steps, or prongs." Puckett v. United States , 556 U.S. 129, 135, 129 S.Ct. 1423, 173 L.Ed.2d 266 (2009).
First, there must be an error or defect-some sort of [d]eviation from a legal rule-that has not been intentionally relinquished or abandoned, i.e., affirmatively waived, by the appellant. Second, the legal error must be clear or obvious, rather than subject to reasonable dispute. Third, the error must have affected the appellant's substantial rights, which in the ordinary case means he must demonstrate that it affected the outcome of the district court proceedings. Fourth and finally, if the above three prongs are satisfied, the court of appeals has the discretion to remedy the error-discretion which ought to be exercised only if the error seriously affect[s] the fairness, integrity or public reputation of judicial proceedings.
*323Id. (alterations in original) (internal citations and quotation marks omitted). The third prong-that the error affected the defendant's substantial rights-"in most cases ... means that the error must have been prejudicial: It must have affected the outcome of the district court proceedings." United States v. Olano , 507 U.S. 725, 734, 113 S.Ct. 1770, 123 L.Ed.2d 508 (1993). "However, for a defendant seeking reversal of his conviction, plain error requires a heightened showing of prejudice."1 United States v. Lalonde , 509 F.3d 750, 759 (6th Cir. 2007).
To "obtain[ ] relief for an unpreserved Rule 11 failing ... a defendant is obliged to show a reasonable probability that, but for the error, he would not have entered the plea."2 United States v. Dominguez Benitez , 542 U.S. 74, 76, 124 S.Ct. 2333, 159 L.Ed.2d 157 (2004). "A defendant must thus satisfy the judgment of the reviewing court, informed by the entire record, that the probability of a different result is sufficient to undermine confidence in the outcome of the proceeding." Id. at 83, 124 S.Ct. 2333 (citation and internal quotation marks omitted). If the defendant can meet this showing, then " 'where the error involves the defendant's state of mind ... the appropriate remedy is to vacate the plea and remand so that the defendant can plead anew' if he chooses, or proceed to trial." United States v. Reader , 254 Fed.Appx. 479, 482 (6th Cir. 2007) (quoting United States v. Tunning , 69 F.3d 107, 115 (6th Cir. 1995) ).
C. Knowingness of Ataya's Guilty Plea as a Whole
Ataya argues that his conviction should be vacated because his guilty plea was not knowing and voluntary due to his lack of notice regarding the immigration consequences of his plea. Appellant Br. at 7, 9, 13. Ataya's argument that his plea was uninformed is entangled with his argument that the district court made a Rule 11 error.3 Appellee Br. at 12; Appellant Reply Br. at 1-2.
*324Federal Rule of Criminal Procedure 11(b)(1)(O) instructs the district court "to inform the defendant of, and determine that the defendant understands ... that, if convicted, a defendant who is not a United States citizen may be removed from the United States, denied citizenship, and denied admission to the United States in the future." This provision was added to the rules in 2013, following the Supreme Court's decision in Padilla v. Kentucky , 559 U.S. 356, 130 S.Ct. 1473, 176 L.Ed.2d 284 (2010). Fed. R. Crim. P. 11(b)(1)(O) Advisory Committee's Note. "The amendment requires the court to include a general statement that there may be immigration consequences of conviction in the advice provided to the defendant before the court accepts a plea of guilty or nolo contendre." Id. (emphasis added). Rule 11(b)(1)(O) mandates that the district court provide this "generic warning" to "every defendant , without attempting to determine the defendant's citizenship."4 Id. (emphasis added). Thus, it is error if the district court fails to provide this warning during any defendant's plea colloquy.
The government concedes that the district court in this case did not comply with Rule 11(b)(1)(O) and that, therefore, Ataya has met the first two prongs of plain-error review; in other words, the failure of the district court to give the warning required by Rule 11(b)(1)(O) was an unwaived error and it was clear or obvious. Appellee Br. at 9. Instead, the government argues that Ataya cannot meet the third step of plain-error review: the government asserts that Ataya does not demonstrate that he would not have pleaded guilty but for the district court's Rule 11 error. Appellee Br. at 10.
Ataya, a native of Syria, is a naturalized American citizen. Pre-Sentence Report at 3. His conviction exposes him to the possibility of denaturalization under 8 U.S.C. § 1101(f)(3) and (8). Appellant Br. at 12; Ataya , 869 F.3d at 402. Ataya argues that he had no notice-from any *325source-that his guilty plea might result in his denaturalization and that, if the district court had complied with Rule 11(b)(1)(O), it is "reasonably likely" he would not have pleaded guilty. Appellant Br. at 13. This argument requires the reasonable inference that, if the district court had properly informed Ataya that a non-United States citizen might face immigration consequences from a guilty plea, Ataya would be on notice that he might face adverse immigration consequences as a naturalized United States citizen and that, once on notice, it is reasonably likely that he would not have pleaded guilty.
The Supreme Court has recognized that American citizenship provides "priceless benefits." Schneiderman v. United States , 320 U.S. 118, 122, 63 S.Ct. 1333, 87 L.Ed. 1796 (1943). The consequences of denaturalization are:
more serious than a taking of one's property, or the imposition of a fine or other penalty. For it is safe to assert that nowhere in the world today is the right of citizenship of greater worth to an individual than it is in this country. It would be difficult to exaggerate its value and importance. By many it is regarded as the highest hope of civilized men.
Id. Furthermore, the Supreme Court has repeatedly acknowledged that "preserving [an individual's] right to remain in the United States may be more important to [that individual] than any potential jail sentence." Lee v. United States , --- U.S. ----, 137 S.Ct. 1958, 1968, 198 L.Ed.2d 476 (2017) (quoting Padilla , 559 U.S. at 368, 130 S.Ct. 1473 ).
In addition to the inherently severe consequences of denaturalization on any individual in general, there is sufficient contemporaneous evidence in the record demonstrating a reasonable probability that Ataya in particular would not have pleaded guilty if he had notice of the potential adverse immigration consequences. At his sentencing hearing, Ataya articulated a strong, and very reasonable, aversion to his former homeland of Syria. R. 198 (Sent. Hr'g Tr. at 22) (Page ID #1544). His relatives who had remained in Syria after he emigrated are now displaced in numerous other countries due to the ongoing civil war. Id. Furthermore, Ataya is the father of three minor children who reside in the United States, is an active parent, and is the family's breadwinner. Id. at 19, 22 (Page ID #1541, 1544); Pre-Sentence Report at 11. Considering the especially serious consequences of denaturalization on Ataya and his family, Ataya has shown that there is a "reasonable probability" that, but for the district court's failure to comply with Rule 11(b)(1)(O), he would not have entered the guilty plea.5
*326Dominguez Benitez , 542 U.S. at 76, 124 S.Ct. 2333. Thus, Ataya has met the third prong of the plain-error test.
Because Ataya has satisfied the first three prongs of plain-error review, it is within our discretion to vacate his conviction "if the error seriously affect[s] the fairness, integrity or public reputation of judicial proceedings." Puckett , 556 U.S. at 135, 129 S.Ct. 1423 (alteration in original). The Advisory Committee on Rules of Criminal Procedure adopted Rule 11(b)(1)(O) after the Supreme Court's decision in Padilla because it was "good policy." Fed. R. Crim. P. 11(b)(1)(O) Advisory Committee's Note. This change in the Rules was not mandated by the decision in Padilla ; rather, the addition is evidence that the Committee believed that knowledge about immigration consequences would enhance "the fairness, integrity or public reputation" of plea colloquies. Rule 11 is designed to prevent defendants from making unknowing or involuntary decisions. A plea colloquy that does not put the defendant on notice that pleading guilty will expose him to the loss of his American citizenship harms the fundamental purpose of the judicial proceeding.
III. CONCLUSION
The district court's failure to comply with Rule 11(b)(1)(O) was plain error.6 Because the plea agreement is not valid, neither is the appellate waiver contained within it; they both fall together. For the foregoing reasons, we hold that the appellate-waiver provision of Ataya's plea agreement is unenforceable, deny the government's motion to dismiss, REVERSE the defendant's conviction, and REMAND for further proceedings consistent with this opinion.