Eric Daniel Anderson appeals the sentence imposed after he pleaded guilty to being a felon in possession of a firearm. Anderson argues the district court’s imposition of a U.S.S.G. § 2K2.1(b)(4) enhancement to his sentence violated his Sixth Amendment rights as recognized in United States v. Booker, 543 U.S. 220, 125 S.Ct. 738, 160 L.Ed.2d 621 (2005). Because Anderson properly preserved a Booker objection and was erroneously sentenced under a mandatory Guidelines scheme, his sentence violated Booker. See United States v. Thomas, 422 F.3d 665, 669 (8th *880 Cir. 2005) (district court committed error both in basing sentence on enhancements found by court at sentencing, and in failing to treat Guidelines as advisory). We conclude the error was not harmless, because the government failed to show the error did not affect Anderson’s substantial rights. See United States v. Haidley, 400 F.3d 642, 644-45 (8th Cir. 2005). Anderson was sentenced at the bottom of the Guidelines range and we disagree with the government contention that the district court’s statements indicate the court would have given the same sentence under an advisory system. To the contrary, taken in context, the court’s statements reflect an intent to be lenient within its perceived discretion. See id. (holding not harmless district court’s error in imposing sentence under mandatory Guidelines regime where court “made conscious decision” to sentence defendant to bottom of Guidelines range and defendant had raised several mitigating facts). Accordingly, we vacate the sentence and remand for resentencing.