The Government appeals the sentence of Richard Kelly Hughes, who pled guilty in the United States District Court for the Western District of Kentucky to one count of being a felon in possession of a firearm, one count of entering a military reservation for an unlawful purpose, and one count of possessing marijuana. The Government argues that the district court erred in departing downward from the applicable sentencing guideline range after concluding from the bench that Hughes’ prior felony conviction for escape from a county jail was a relatively benign “crime of violence.” Because the district court did not provide written reasons for its departure, we VACATE the district court’s sentence and REMAND the case for resentencing.

I.

On November 10, 2001, Defendant Hughes was stopped on Fort Campbell Military Base while carrying a loaded 7mm Ruger rifle, a lock-blade knife, and two bags of marijuana. Hughes was later indicted on one count of being a felon in possession of a firearm in violation of 18 U.S.C. § 922(g)(1), one count of entering a military reservation for an unlawful purpose in violation of 18 U.S.C. § 1382, and one count of possessing marijuana in violation of 18 U.S.C. § 844(a). On April 7, 2003, Hughes agreed to enter a plea of guilty to the three counts. The United States agreed to recommend a sentence at the lowest end of the applicable Sentencing Guideline range and stated that it would recommend a reduction of 2 or 3 levels below the applicable guideline for “acceptance of responsibility.”

The Government and Hughes indicated in the Plea Agreement that they believed Hughes had a total offense level of 13. The parties arrived at this number by starting with the prescribed base offense level of 14 for a felon in possession offense under U.S.S.G. § 2K2.1(a)(6), adding 2 levels under § 2K2.1(b)(4) because the firearm was stolen, and subtracting 3 levels for acceptance of responsibility under § 3E1.1. As is custom, the parties acknowledged that their guideline calculation was “not binding” upon the district court.

Hughes’ Probation Officer submitted a Presentence Report (“PSR”) which contained the details of Hughes’ prior convictions. The report indicated that Hughes had three prior felony burglary convictions, a prior felony conviction for escape from the Dyer County (TN) Jail, a prior felony conviction for destruction of utility appliances, and two prior convictions for driving with a revoked license. The Probation Officer calculated Hughes’ base offense level at 20, rather than 14, because *612Hughes’ prior escape conviction indicated that he had committed the instant offense “subsequent to sustaining one felony conviction of either a crime of violence or a controlled substance offense.” U.S.S.G. § 2K2.1(a)(4)(A). The PSR added 2 levels because the firearm was stolen and then subtracted 3 levels for acceptance of responsibility. Hughes’ total offense level, according to the PSR, was 19 and his Criminal History Category was VI based on Hughes’ prior adult criminal convictions. Given these calculations, the PSR concluded that Hughes faced a Sentencing Guideline range of 63 to 78 months.2

Hughes objected to the PSR, arguing that his prior escape conviction did not constitute a crime of violence. In an addendum to Hughes’ objection, the Probation Office disagreed, citing United States v. Harris, 165 F.3d 1062, 1068 (6th Cir. 1999), in which this Court said that, under a “categorical” approach, an escape conviction is a conviction for a “crime of violence” for purposes of the Sentencing Guidelines. The Probation Office also noted that, contrary to Hughes’ contention, he was not entitled to have his offense level computed pursuant to the “lawful sporting purposes” provision because he had previously committed a crime of violence. U.S.S.G. § 2K2.1, cmt. n. 10.

At the September 5, 2003 sentencing, the district court agreed with the PSR that under Harris, “escape is a crime of violence,” and specifically found that “it’s a crime of violence” in this case. (Joint Appendix, 96). Because Hughes unlawfully possessed a firearm after having been convicted of a crime of violence, the district judge determined that Hughes’ base offense level should be 20 under § 2K2.1. The district court also applied a 2 level enhancement because the gun Hughes possessed was stolen. Hughes moved for a downward departure based on his prior good character and good citizenship, which the district court denied. The court then found that Hughes’ total offense level was 193 and his criminal history category was VI. The court also indicated that the guideline range was 63-78 months custody.

When discussing Hughes’ 1991 escape conviction, the court stressed Hughes’ young age at the time of the escape and that his actions involved “no threats of harm to anyone.” (J.A., 96). The court stated that a downward departure was in order, “considering all ... the relevant facts [,] ... the circumstances surrounding the escape, and ... but for the escape, he probably would have been serving two or three months in jail.” (J.A., 98). The court then imposed a prison sentence of 12 months and one day. The written judgment that followed did not contain a statement of reasons for the departure, nor did it identify Hughes’ offense level or Criminal History Category.

II.

Section 401(d)(2) of the Prosecutorial Remedies and Other Tools to End the Exploitation of Children Today Act of 2003 (“PROTECT Act”) changed the standard of review for decisions to depart from the Sentencing Guidelines. United States v. Camejo, 333 F.3d 669, 675 (6th Cir. 2003). Prior to the PROTECT Act, this Court reviewed the decision by a district court to *613depart for an abuse of discretion. Id. However, under the PROTECT Act, the decision to depart from the Sentencing Guidelines is reviewed de novo if the district court’s sentence is outside the applicable guideline range and: a) the court failed to provide a written statement of reasons for its departure, or; b) the sentence departs based on a factor that is not justified by the facts of the case. See 18 U.S.C. §§ 3742(e);3 4 see also Camejo, 333 F.3d at 675 (“The PROTECT Act now requires the sentencing court to provide in the written order of judgment the ‘specific reason’ for departing from the guidelines”).

The sentencing court in this case provided a downward departure for Hughes based on Harris. In Harris, we noted that although an escape conviction is to be treated as a crime of violence for purposes of the Sentencing Guidelines,

we do not exclude the possibility that a limited inquiry into his actual conduct at the time of his escape from the Shelby County Correctional Center, coupled with other relevant facts, might appropriately lead the sentencing court to conclude that a downward departure is warranted here.

Harris, 165 F.3d at 1069.

The Government correctly notes that the district court, after finding that Hughes had a total offense level of 19, effectively departed 13-14 levels to a total offense level of 5-6 when it imposed a sentence of 12 months and 1 day.5 The Government also points out that if the escape conviction had never occurred, Hughes’ base offense level would have been 14. Assuming the district court would hold constant its 2 level addition for the stolen gun and 3 level subtraction for acceptance of responsibility, Hughes’ total offense level would have been 13 with a corresponding sentencing range of 33-41 months. With these considerations in mind, the Government argues that the district court erred in granting such a large downward departure. The Government also contends that the district court’s failure to provide written reasons for its departure requires de novo review under the PROTECT Act. We agree and remand the case for resentencing.

In ruling that the district court erred, we express no view on whether the circum*614stances surrounding Hughes’ escape justify some degree of downward departure under Hams. However, the Court has difficulty discerning how a departure to level 5 or 6 is justified considering that even if the escape conviction is totally removed from consideration, Hughes’ total offense would be 13, after making the adjustments for the stolen gun and acceptance of responsibility. The Court therefore remands the case for resentencing and instructs the district court that in the event the court departs downward, it must provide written reasons for the departure pursuant to 18 U.S.C. § 3742(e).

III.

For the foregoing reasons, the district court’s sentence imposed on Defendant Richard Hughes is VACATED and REMANDED for resentencing consistent with this opinion.