MURPHY, Circuit Judge.

Mike Gutierrez was convicted by a jury of conspiracy to distribute and possess between 50 and 500 grams of methamphetamine, and he was sentenced to 168 months in the period between Blakely v. Washington, 542 U.S. 296, 124 S.Ct. 2531, 159 L.Ed.2d 403 (2004), and United States v. Booker, 543 U.S. 220, 125 S.Ct. 738, 160 L.Ed.2d 621 (2005). Although the district court treated the sentencing guidelines as mandatory, it considered the jury finding of drug quantity to be binding. It declined to hold Gutierrez responsible for more drugs or to apply a firearm enhancement, but it enhanced his sentence for obstruction of justice on the assumption that the guilty verdict meant the jury had found his testimony to be false. Both parties attribute error to this enhancement. Gutierrez also claims his criminal history score was miscalculated, and the government argues that the district court erred by refusing to apply a firearm enhancement or make an independent determination of drug quantity. We vacate and remand for resentenc-ing.

On October 23, 2003 Gutierrez was charged with conspiracy to distribute 500 grams or more of a mixture containing methamphetamine, in violation of 21 U.S.C. § 846. Evidence was introduced at trial to show that Gutierrez had bought and sold methamphetamine on numerous occasions over an extended period of time, that he had exchanged methamphetamine for firearms, and that he had been seen with a shotgun at the place from which he distributed methamphetamine. Gutierrez testified and denied being involved in such activities.

The jury was instructed that in order to find Gutierrez guilty it had .to find all necessary elements of conspiracy as well as the quantity of drugs involved in the offense, whether it was 0 to 50 grams, 50 to 100 grams, or more than 500 grams of methamphetamine. The jury found Gutierrez guilty of conspiracy to distribute 50 to 500 grams of methamphetamine, in violation of 21 U.S.C. §§ 841(a)(1) and 841(b)(1), and the district court found under 21 U.S.C. § 851 that he had had a prior felony drug conviction.

Sentencing hearings were held on September 1 and December 1, 2004. The district court stated that the sentencing guidelines were constitutional and that “[wjhether we like them or not, whether we agree with them or not, we are not free to depart from them.” The court proceeded to sentence Gutierrez under the mandatory guideline scheme. The government requested the court make its own determination of the drug quantity attributable to Gutierrez, arguing that Blakely did not apply to the guidelines and that the Sixth Amendment did not bar a judge from making sentencing findings. The court considered itself bound by the jury’s verdict finding Gutierrez responsible for 50 to 500 grams of methamphetamine and refused to make an independent determination. This gave Gutierrez a base offense level of 30.

'The district court then considered the government’s request for enhancements for obstruction of justice and possession of a weapon in connection with the offense. Gutierrez objected under Blakely to the application of an obstruction of justice enhancement under USSG § 3C1.1 because it had not been charged in the indictment or found by the jury, but the court reasoned that the jury had implicitly decided' that Gutierrez had lied under oath while testifying at trial and imposed an obstruction enhancement. Gutierrez responded to the government’s USSG § 2Dl.l(b)(l) request for a firearm enhancement by argu *736 ing that it would be improper under Blakely because the underlying facts had not been found by a jury or admitted by him. The court agreed with his argument and found his total offense level to be 32.

Gutierrez’s criminal history score had been originally calculated as category VI, but the district court reduced his criminal history points from thirteen to nine after learning that the records for two of his prior convictions were not available. Although Gutierrez objected to the inclusion under USSG § 4Al.l(e) of two points for committing the instant offense within two years of release from imprisonment, he conceded that his criminal history category would remain the same whether he had seven or nine criminal history points. With-a total offense level of 32 and a criminal history category of IV, his guideline sentencing range was 168 to 210 months. The court sentenced him at the low point to 168 months.

The parties appeal the district court’s ruling on several grounds. Both sides agree that the district court committed Booker error by treating the guidelines as mandatory and by applying an enhancement for obstruction of justice based upon the jury’s general verdict. The government also argues that the district court erred by refusing to make its own independent determination as to the amount of drugs for which Gutierrez was accountable and as to whether he possessed a weapon in connection with his drug offense. On his appeal Gutierrez continues to argue that the district court erred in including two criminal history points for committing this offense within two years of release from confinement.

Since the parties preserved their claims of error under the Sixth Amendment and Booker, our review is for harmless error. United States v. Archuleta, 412 F.3d 1003, 1005 (8th Cir.2005). This “requires a determination as to whether the error affected substantial rights... meanfing] whether [it] was prejudicial or affected the outcome of the district court proceedings.” United States v. Sayre, 400 F.3d 599, 600-01 (8th Cir.2005). The party benefitting from the error has the burden to prove that it was harmless. United States v. Red Elk, 426 F.3d 948, 950 (8th Cir.2005); United States v. Haidley, 400 F.3d 642, 644 (8th Cir.2005) (“The burden of proving that an error does not affect substantial rights is upon the ‘beneficiary of the error’ ”) (citing Chapman v. California, 386 U.S. 18, 24, 87 S.Ct. 824, 17 L.Ed.2d 705 (1967)).

Both parties complain that the district court erred under the Sixth Amendment by treating the jury verdict as requiring an enhancement for obstruction of justice, and we agree. Although Booker followed Blakely and Apprendi v. New Jersey, 530 U.S. 466, 120 S.Ct. 2348, 147 L.Ed.2d 435 (2000), in holding that “[a]ny fact, (other than a prior conviction) which is necessary to support a sentence exceeding the maximum authorized by the facts established by.. .a jury verdict must be admitted by the defendant or proved to a jury beyond a reasonable doubt,” 125 S.Ct. at 756, the Court observed in its remedial opinion that a sentencing enhancement can constitutionally be based on a court finding so long as the sentencing guidelines are treated as advisory. Id. at 764-65; see also United States v. Garcia-Gonon, 433 F.3d 587 (8th Cir.2006); United States v. Morell, 429 F.3d 1161, 1164 (8th Cir.2005). The government concedes that the enhancement for obstruction did not comply with Booker and was not harmless.

The government complains that the district court also erred by refusing to make independent determinations as to the quantity of drugs for which Gutierrez was *737 responsible and as to whether he possessed firearms during his offense. Under Booker, 125 S.Ct. at 764-67, the sentencing court starts by calculating a guideline sentence, then considers possible departures and the 18 U.S.C. § 3553(a) factors before deciding on a sentence either within or outside the advisory guideline range. United States v. Haack, 403 F.3d 997, 1002-03 (8th Cir.2005). Judicial fact finding is permitted under the advisory guidelines, see id. at 1003; Morell, 429 F.3d at 1164, but treating them as mandatory and subject only to fact finding by the jury is Booker error. See Booker, 125 S.Ct. at 760, 763; United States v. Thomas, 422 F.3d 665, 669 (8th Cir.2005).

As the beneficiary of this Booker error, Gutierrez must show that his sentence was not substantially influenced by it, Haidley, 400 F.3d at 645, and he has not met that burden. The presentence report recommended that Gutierrez be held responsible for at least 1.5 kilograms of methamphetamine with a base offense level of 34, and enhancements of four levels for obstruction of justice and possession of a firearm. Had these enhancements been applied, Gutierrez would have had a total offense level of 38 rather than 32 and a guideline range of 324 — 405 months instead of 168 — 210 months. We thus cannot say that the error did not substantially affect his sentence. See id. Since the guideline calculations could have been very different if the district court had realized that it could constitutionally find Gutierrez accountable for a greater drug quantity than the jury and for possessing a weapon during his offense, we conclude the errors were not harmless.

Finally, Gutierrez challenges the district court’s inclusion of two points in his criminal history score under USSG § 4Al.l(e), for committing this offense within two years of being released from confinement. He argues that under Blakely the court could not make the finding necessary to add these points (a finding that he was subject to increased punishment by reason of prior convictions under 21 U.S.C. § 851(d)). A prior conviction need not be submitted to a jury or proved beyond a reasonable doubt for it to be considered for sentencing purposes. Booker, 125 S.Ct. at 756. Even though Gutierrez objected to the inclusion of these two points, he did not object to the records of his prior convictions, and he admitted that these additional two points did not affect his criminal history category. We thus conclude that even if it had been error to include these two criminal history points, the error would be harmless since it did not alter the guideline range. See USSG § 5 Sentencing Table.

Accordingly, we vacate the judgment of the district court and remand for resen-tencing consistent with this opinion.