BEEZER, Circuit Judge:

Ronald Henderson pleaded guilty to being a felon in possession of a firearm. Henderson has prior convictions for murder and child molestation. At Henderson's sentencing, the district court found that Henderson did not qualify as a career offender. The court made the preliminary finding that Henderson's base offense level was 12 and with acceptance of responsibility his adjusted offense level was 10; the court also found Henderson had a category IV criminal history.

The district court stated that Henderson's criminal history category under-represented the seriousness of his past actions. However, instead of raising Henderson's criminal history category, the court raised the offense level to 16. This gave Henderson a guideline range of 33 to 41 months; the court sentenced Henderson to 37 months. Henderson appeals the grounds and the manner of the upward departure.

I

Departure from the Sentencing Guidelines is reviewed de novo. Williams v. United States, ___ U.S. ___, ___, 112 S.Ct. 1112, 1120, 117 L.Ed.2d 341 (1992). Under Williams, we must first determine whether the sentence was in violation of law or an incorrect application of the guidelines; second, we must determine whether the departure was unreasonably high or low from the relevant guideline. Id.

We review guideline departures under a three part test. United States v. Lira-Barraza, 941 F.2d 745 (9th Cir. 1991) (en banc). First, we must determine if the district court had legal grounds to depart. The district court may depart from the guidelines only if it identifies an aggravating circumstance not adequately taken into consideration by the Sentencing Commission. Id. at 746. Second, we review the factual findings of the district court for clear error. Id. Finally, we review the extent of the departure for reasonableness "in light of the structure, standards and policies of the Act and Guidelines." Id. at 751.

The district court must explain the reasoning for both the direction and degree of the departure in sufficiently specific language to allow appellate review. Id. We "do not search the record for permissible reasons for departure; instead, we analyze the reasons actually given by the district court." United States v. Montenegro-Rojo, 908 F.2d 425, 428 (9th Cir. 1990).

II

The district court must have legal grounds for departure from the guidelines. U.S.S.G. § 4A1.3 permits a sentencing court to consider upward departure when a defendant's criminal history category does not adequately reflect the seriousness of the defendant's past criminal conduct. "The guidelines anticipate that departure will be rare. A factor already calculated into a sentence under the guidelines may not be a proper basis for departure." United States v. Hernandez-Vasquez, 884 F.2d 1314, 1315 (9th Cir. 1989) (citations omitted).

A. Violence of Prior Criminal Conduct

Henderson claims that the sentencing court departed from the guidelines solely due to the nature of Henderson's prior convictions. Although Henderson has only two prior convictions, they are both extremely violent and serious. Henderson argues that this reason for departure is invalid. We agree.

The Seventh Circuit recently rejected an upward departure based on the nature of a defendant's prior criminal conduct. In United States v. Morrison, 946 F.2d 484 (7th Cir. 1991), cert. denied sub nom., Anderson v. United States, ___ U.S. ___, 113 S.Ct. 826, 121 L.Ed.2d 696 (1992), the district court based its upward departure on the fact that one of defendant's prior convictions was a brutal execution style murder. The Seventh Circuit ruled that this was an inappropriate ground for departure because the defendant already received criminal history points for the prior conviction under § 4A1.1.

"[A]n upward departure may be warranted when the defendant has committed crimes or conduct that the criminal history calculation instructions . . . fail specifically to consider." Morrison, 946 F.2d at 496 (citations omitted); U.S.S.G. § 4A1.3. The nonexclusive list of upward departure situations in § 4A1.3 includes foreign convictions (§ 4A1.3(a)), consolidated sentences that are the consequence of a series of serious offenses (§ 4A1.3(b)), misconduct established by civil or administrative adjudication (§ 4A1.3(c)), defendant pending trial, sentencing, or appeal on another charge at time of instant offense (§ 4A1.3(d)), and prior criminal conduct not resulting in a conviction (§ 4A1.3(e)); See United States v. Gayou, 901 F.2d 746, 748 (9th Cir. 1990) (affirming upward departure based on grounds found in § 4A1.3(c), (d), and (e)).

The upward departure for the nature of Henderson's crimes does not fit into the category outlined above. The district court did not believe that the Sentencing Commission overlooked anything in awarding criminal history points; the district court believed that the Sentencing Commission did not assign enough points for these particular offenses. That belief may be morally correct. However, the Sentencing Commission chose to award defendants three criminal history points for every conviction leading to a sentence of greater than one year, regardless of the nature of the underlying offense conduct. See Morrison, 946 F.2d at 496.

Henderson's convictions were counted in the calculation of his criminal history; they were already a factor adequately considered in the guidelines. While we understand the motivation for the district court's departure, the nature of Henderson's past crimes cannot serve as a proper basis for upward departure.

B. Timing

The government claims that the aggravating circumstance not taken adequately into account by the guidelines is one of timing. In this circuit, the crime of being a felon in possession of a firearm was a crime of violence prior to November 1, 1989. United States v. Sahakian, 965 F.2d 740 (9th Cir. 1992). At the same time the Sentencing Commission changed § 4B1.2, it also increased the base offense levels for firearms offenses (U.S.S.G. § 2K2.1).

The 1989 and 1991 versions of §§ 4B1.1 ("Career Offender") and 4B1.2 ("Definitions of Terms Used in Section 4B1.1") are identical. The difference in the two versions comes from the 1991 amendment of Application Note 2 to § 4B1.2. The application note explicitly states that a felon in possession of a firearm is not a crime of violence. However, based on the actual guideline language, the Ninth Circuit read this exclusion into the 1989 version of the guidelines. Sahakian 965 F.2d at 742. The district court incorrectly believed that the status of being a felon of possession changed between time of offense and time of sentencing. It did not.

A district court applies the version of guidelines in effect on date of sentencing except where amendments create an ex post facto problem. When an ex post facto problem does appear, the court sentences the defendant under the version of the guidelines in effect at the time of the offense — in its entirety. United States v. Warren, 980 F.2d 1300, 1304 (9th Cir. 1992). Henderson committed the offense on May 31, 1990; under the 1989 guidelines, Henderson has a total offense level of 10 and a criminal history category of IV (nine criminal history points). The applicable guideline range is 15 to 21 months. Timing cannot justify the upward departure to 37 months imposed by the district court.

III

We find the district court's reasons for the upward departure inadequate. We need not consider Henderson's challenge to the manner in which the district court departed. We VACATE Henderson's sentence and REMAND for resentencing.