BYE, Circuit Judge.

William Greene appeals the eighty-seven month sentence imposed following his guilty plea to possessing with intent to distribute more than fifty grams of cocaine base. Greene argues the district court improperly applied a presumption of reasonableness to the applicable guidelines range. We vacate Greene's sentence and remand for resentencing.

I

On May 17, 2006, Greene was indicted for possession with intent to distribute more than fifty grams of cocaine base in violation of 21 U.S.C. §§ 841(a)(1), (b)(1)(A). Pursuant to a plea agreement, Greene entered a plea of guilty on the single count of the indictment. An initial presentence investigation report ("PSR") concluded Greene's advisory guideline range was 108 to 135 months, based on an adjusted offense level of 31 and a criminal history category of I. The report noted, however, that Mr. Greene faced a ten year statutory minimum sentence that overrode the low-end of this range.

Following concerns over the adequacy of Greene's counsel, the court appointed the Federal Defender Office to represent Greene. Shortly thereafter, Greene submitted to a proffer interview with the government and became eligible for a safety valve reduction. This adjustment eliminated the ten year statutory minimum and reduced Greene's advisory range to 87 to 108 months.

At sentencing, Greene requested a sentence below the applicable guidelines range based on the factors set out in 18 U.S.C. § 3553(a). Specifically, Greene requested a more lenient sentence based on (1) the Sentencing Commission's conclusions regarding the disparity between the penalties for cocaine powder and cocaine base, (2) his age, (3) his medical condition, (4) his prior counsel's deficient representation, and (5) his work record. At the time of sentencing, Greene was sixty years old and was suffering from several health-related problems, including diabetes and hypertension. In addition, Mr. Greene was recovering from a heart attack he suffered in 2004.

The district court noted under current Eighth Circuit law it had very limited discretion in varying from the advisory guideline range. With respect to the circumstances in this particular case, the court concluded Eighth Circuit precedent precluded it from imposing a downward variance from the low-end of the advisory range. The court made clear, however, if it had the opportunity it would have imposed a lower sentence based on United States v. Booker, 543 U.S. 220, 125 S.Ct. 738, 160 L.Ed.2d 621 (2005). The court expressly stated in its Statement of Reasons it did not impose a downward variance from the low-end of the advisory range because it believed it was precluded from doing so under "current Eighth Circuit precedent." Sent. Tr. at 17. The court then sentenced Greene to 87 months, the low-end of the applicable guidelines range.

II

Before reaching the merits of Greene's appeal, we must address the government's motion to dismiss. After oral argument the government filed a motion to dismiss Greene's appeal based on a waiver provision in Greene's plea agreement. We hold the government waived this argument and, therefore, deny the government's motion.

This Court routinely enforces the doctrine of waiver and declines to address arguments a party fails to raise in its opening brief. See, e.g., Hailemichael v. Gonzales, 454 F.3d 878, 886 n. 3 (8th Cir. 2006) (citing Akeyo v. O'Hanlon, 75 F.3d 370, 374 n. 2 (8th Cir. 1996) ("As a general rule, we do not address arguments raised for the first time in a reply brief. . . .")); United States v. Applied Pharmacy Consultants, Inc., 182 F.3d 603, 609 (8th Cir. 1999).

Here, the government did not raise the waiver argument at sentencing in response to Greene's request for a sentence outside the applicable guidelines range. Nor did it raise the argument in its appellate brief. Indeed, the government's brief expressly stated there was no plea agreement. It was not until oral argument that the government, for the first time, suggested Greene's plea agreement foreclosed him from seeking a sentence outside the applicable guidelines range. Because the record makes clear the government waived this argument, we decline to address it here. See Latorre v. United States, 193 F.3d 1035, 1037 n. 1 (8th Cir. 1999) (declining to address whether appellant's appeal was precluded by a waiver provision in the appellant's plea agreement because the government had failed to raise the issue in the district court or in the appeal). Instead, we proceed to the merits of Greene's claim.

III

This court reviews a district court's sentence determination under an abuse-of-discretion standard. The United States Supreme Court recently clarified the scope of our review:

[T]he appellate court . . . must first ensure that the district court committed no significant procedural error, such as failing to calculate (or improperly calculating) the Guidelines range, treating the Guidelines as mandatory, failing to consider the § 3553(a) factors, selecting a sentence based on clearly erroneous facts, or failing to adequately explain the chosen sentence-including an explanation for any deviation from the Guidelines range. Assuming that the district court's sentencing decision is procedurally sound, the appellate court should then consider the substantive reasonableness of the sentence imposed under an abuse-of-discretion standard.

Gall, ___ U.S. ___, 128 S.Ct. 586, 597, 169 L.Ed.2d 445 (2007). See also Koon v. United States, 518 U.S. 81, 100, 116 S.Ct. 2035, 135 L.Ed.2d 392 (1996) ("The abuse-of-discretion standard includes review to determine that the discretion was not guided by erroneous legal conclusions.").

According to Greene, the record demonstrates the district court interpreted this court's binding precedent to require application of a presumption of reasonableness to the applicable guidelines range and to preclude a variance in the absence of extraordinary circumstances. As the Supreme Court made clear in Rita v. United States, ___ U.S. ___, 127 S.Ct. 2456, 168 L.Ed.2d 203 (2007), the presumption of reasonableness is an appellate presumption and "the sentencing court does not enjoy the benefit of a legal presumption that the Guidelines sentence should apply." Id. at 2465. See also United States v. Wilms, 495 F.3d 277, 282 (6th Cir. 2007) (reversing and remanding defendant's sentence due to the district court's imposition of a presumption of reasonableness in violation of Rita); United States v. Foreman, 436 F.3d 638, 644 n. 1 (6th Cir. 2006) ("[A] district court's job is not to impose a `reasonable' sentence. Rather, a district court's mandate is to impose `a sentence sufficient, but not greater than necessary, to comply with the purposes' of section 3553(a)(2). Reasonableness is the appellate standard of review in judging whether a district court has accomplished its task.").

The record in this case makes clear the district court applied a presumption of reasonableness to the applicable guidelines range. At sentencing, the district court stated, "I do not believe based on current Eighth Circuit law that I am permitted to do a variance in this case. However, if I had an opportunity to do a variance based on Booker, I would have done so." Sent. Tr. at 17. The district court also said it would await the Supreme Court's decision in Rita "to figure out whether I have some discretion or whether really I'm pretty much bound by the federal sentencing guidelines unless there's something that they haven't taken into account." Id. at 19.

In light of Rita, the district court's application of a presumption of a reasonableness was a significant procedural error. See Gall, 128 S.Ct. at 597. The district court imposed the sentence, not as a result of the district court's assessment of the relevant factors and determination of the minimally adequate sentence, as required by § 3553(a), but as a direct consequence of the court's incorrect conclusion it was bound by Eighth Circuit precedent to accord the guidelines range presumptive weight. See Koon, 518 U.S. at 100, 116 S.Ct. 2035 ("A district court by definition abuses its discretion when it makes an error of law.") (citing Cooter Gell v. Hartmarx Corp., 496 U.S. 384, 403-05, 110 S.Ct. 2447, 110 L.Ed.2d 359 (1990)).

Further, we do not believe this error was harmless. The government bears the burden of proving the district court's error was harmless and must show that no "grave doubt" exists as to whether the error substantially influenced the outcome of the proceedings. United States v. Cullen, 432 F.3d 903, 905-06 (8th Cir. 2006) (citations omitted). The record makes clear had the district court properly exercised its discretion, it would have found that the relevant factors and purposes compelled a sentence below the advisory Guidelines range. Sent. Tr. at 17 ("[I]f I had an opportunity to do a variance based on Booker, I would have done so."). Given the record, we conclude the error substantially influenced the outcome of the proceedings and, therefore, was not harmless.

IV

Accordingly, we vacate Greene's sentence and remand for resentencing consistent with this opinion.