OPINION
RICE, District Judge.This is a criminal prosecution brought under 42 U.S.C. § 408(a)(4), for fraudulent use of a Social Security number. The Defendant pled guilty. At sentencing, the *60district court granted Defendant’s motion for a downward departure. The matter is before this Court on the Government’s appeal from the district court’s downward departure. For the reasons assigned herein, the district court erred in granting the downward departure, and the sentence imposed is reversed, and this matter is remanded for re-sentencing in accordance with this opinion.
I. Background
Defendant Gladys M. Burrus had been appointed by the Social Security Administration as the Representative Payee for her uncle, Fisher Westmoreland. Westmoreland died on March 21,1987, but Burrus continued to cash his Social Security retirement checks for fifteen years, until June, 2002.1 Burrus pled guilty to one count under 42 U.S.C. § 408(a)(4).
In 1989, Burrus was convicted for attempted theft by deception, a misdemean- or. She committed the instant offense while on probation for that prior offense, thereby adding two points to her criminal history score, placing her in criminal history category II under the United States Sentencing Guidelines (the “Sentencing Guidelines”). Her offense level was calculated to be 14, after a two-level adjustment for acceptance of responsibility, resulting in a prescribed sentence range of twelve to eighteen months, a fine of $3,000 to $30,000, and a term of supervised release of two to three years.
Burrus filed a motion for downward departure, alleging that criminal history category II significantly over-represented the seriousness of her criminal history or the likelihood that she would commit further crimes. The Government opposed the motion.
The district court sustained Burruss’s motion for downward departure. Based on its departure, it sentenced Burrus to five months incarceration.
-II. Standard of Review
The determination that a certain criminal history category significantly over-represents the seriousness of a defendant’s past criminal conduct or the likelihood of recidivism is reviewed de novo. Until recently, courts of appeals were to “give due deference to the district court’s application of the guidelines to the facts,” applying the deferential “abuse of discretion” standard of review. Koon v. United States, 518 U.S. 81, 96-100, 116 S.Ct. 2035, 135 L.Ed.2d 392 (1996). However, last year, Congress amended 18 U.S.C. § 3742(e) to require that, under certain circumstances, namely, determinations under 18 U.S.C. § 3742(e)(3)(A) and (B), the appellate court must review de novo the district court’s application of the guidelines to the facts. Subsections (3)(A) describe a sentence that:
(3) is outside the applicable guideline range, and
(A) the district court failed to provide the written statement of reasons required by section 3553(c);
(B) the sentence departs from the applicable guideline range based on a factor that—
(i) does not advance the objectives set forth in section 3553(a)(2); or
(ii) is not authorized under section 3553(b); or
(iii) is not justified by the facts of the case.
*6118 U.S.C. § 3742(e)(3). The sentence at issue here implicates both of these subsections. The district court’s findings of facts are still reviewed on the clearly erroneous standard.
On appeal, Burrus does not argue that employing de novo review in this case would constitute a violation of the Ex Post Facto Clause, nor does it seem evident that applying the standard of review imposed by the recent amendment would constitute such a violation. “A change in the standard of review is properly characterized as procedural rather than substantive [and therefore can be applied to a pending appeal without violating the Ex Post Facto Clause] because it neither increases the punishment nor changes the elements of the offense or the facts that the government must prove at trial.” U.S. v. Hutman, 339 F.3d 773, 775 (8th Cir.2003) (rejecting challenge under the Ex Post Facto Clause to application of the amended § 3742(e)), quoting U.S. v. Mejia, 844 F.2d 209, 211 (5th Cir.1988).
III. Analysis
The district court’s initial determination that Defendant’s criminal history falls under category II is not in serious dispute. The Government does dispute, however, the district court’s rationale for departing downward. At the sentencing colloquy, the district court stated:
In reviewing this matter, I found that the Court may depart where the criminal history category is significantly over[-]represented by — over — represents the seriousness of the defendant’s criminal history or likelihood that the defendant will commit further crimes. The background commentary in the sentencing guidelines recognizes that there are significant limitations in mathematical approaches to criminal history. The criminal history category is unlikely to take into account all variations in the seriousness of the criminal history that may occur. Therefore, the Court’s discretion in overstatement cases is broader than it is with respect to other departure issues.
According to the guideline commentary, the Court need not find that the facts take the case out of the heartland, but only that the information is reliable and that it indicates either significant over-representation of the seriousness of the crime or the likelihood that the defendant will commit further crimes. Matters that can bear on whether the criminal history category over — represents either the serious of the criminal history or the likelihood of future crimes include instances, for example, of addiction, which are not a factor in this case, or remoteness of time, and here the single misdemeanor conviction occurred 15 years ago, or lack of relatedness to the prior offense. The misdemeanor here was arguably close to the instant offense.
Nonetheless, I have considered the record. The court will sustain the motion for the downward departure under § 4A1.3. That motion is sustained.
From this, having ruled out issues pertaining to addiction and lack of relatedness of the prior offense to the instant offense, it appears that the district court believed that the remoteness of time of the previous offense was at stake here.2
*62Quite simply, the district court was incorrect in stating that it need not find the case to be outside the heartland in order to depart downward. 18 U.S.C. § 3553(b) states that a sentencing court is to impose a sentence within the prescribed range “unless the court finds that there exists an aggravating or mitigating circumstance of a kind, or to a degree, not adequately taken into consideration by the Sentencing Commission in formulating the guidelines that should result in a sentence different from that described.” Further, the Introduction to the Sentencing Guidelines indicates that “[t]he Commission intends the sentencing courts to treat each guideline as carving out a ‘heartland,’ a set of typical cases embodying the conduct that each guideline describes.” U.S.S.G. Ch. 1, Pt. A(4)(b).
Burrus responds that the word “heartland” is not a talisman, and cites cases in which district courts have departed downward, citing § 4A1.3 as the basis for the departure, without using the exact word “heartland.” However, as the Government suggests, it is not merely the case that the district court substituted § 4A1.3 for heartland analysis. Instead, the court expressly disclaimed and denied the necessity of finding that the circumstances of this case remove it from the heartland of cases — i.e., the court essentially denied that it was obligated to find that the circumstances herein differ from the “set of typical cases embodying the conduct that each guideline describes.”
Moreover, the fact that, in this case, this Court reviews de novo the application of the Sentencing Guidelines to the facts enables us to review the propriety of the district court’s downward departure, regardless of the labels affixed to its rationale. In this regard, even if the district court did not intend to forsake the heartland analysis, we agree with the Government that there was an insufficient basis in this case for departing downward from the sentence imposed by the Sentencing Guidelines.
In arguing as to whether a downward departure was justified, both sides rely on § 4A1.3’s Policy Statement, which contains the following:
There may be cases where the court concludes that a defendant’s criminal history category significantly over-represents the seriousness of a defendant’s criminal history or the likelihood that the defendant will commit further crimes. An example might include the case of a defendant with two minor misdemeanor convictions close to ten years prior to the instance offense and no other evidence of prior criminal behavior in the intervening period. The court may conclude that the defendant’s criminal history was significantly less serious than that of most defendants in the same criminal history category (Category II), and therefore consider a downward departure from the guidelines.
U.S.S.G. § 4A1.3. The Government notes the dissimilarity between this example and the case before the Court. Whereas the example contained in the policy statement envisions a defendant with prior convic*63tions nearly ten years prior to the instant offense, with no evidence of prior criminal behavior in the intervening period, the record indicates that Burras continued fraudulently cashing her deceased uncle’s Social Security checks for the entirety of the 13 years that elapsed between her misdemeanor conviction and her conviction in the present matter.3 Accordingly, the facts regarding Burrus’s criminal history simply do not resemble the facts given by the Sentencing Guidelines that exemplify a criminal history categorization that over-represents a defendant’s criminal history.
Burras responds by pointing to another example used later in § 4A1.3’s policy statement, where the Sentencing Guidelines state that “a defendant with nine prior 60-day jail sentences for offenses such as petty larceny, prostitution, or possession of gambling slips has a higher number of criminal history points (18 points) than the typical Criminal History Category VI defendant, but not necessarily a more serious criminal history overall.” Id. Burras believes that this stands for the general proposition that some crimes are more serious than others and therefore supports the district court’s downward departure. Yet, this reasoning is faulty. Whether or not it is true that § 4A1.3 stands for the general proposition that some crimes are more serious than others, Burras points to no authority that would support a finding that her prior conviction for attempted theft by deception is the sort of exceedingly minor past offense that would purportedly trigger this basis for departing downward. Moreover, there is simply no basis in the record for concluding that such was the basis of the district court’s downward departure. In fact, as noted supra, the record demonstrates otherwise, in that the district court suggested that a downward departure was appropriate due to the remoteness in time of Burrus’s prior conviction. For the reasons noted above, however, this rationale cannot justify a downward departure because it is based on the erroneous conclusion that a substantial period of time elapsed between Burrus’s prior conviction and the conviction at issue here. Instead, in essence, no time passed between those two convictions, in that Burras actively defrauded the Social Security Administration immediately following her conviction in 1989, and continued to do so for 13 years. Section 4A1.2(e) of the Sentencing Guidelines establishes the applicable time period for determining the effect of prior sentences. Therefore, the remoteness in time of a prior offense cannot be the basis of a downward departure, as it is most definitely not the case that the Sentencing Commission did not consider the date of the prior offense in determining its effect on a defendant’s criminal history score. See 18 U.S.C. § 3553(b).
Accordingly, the sentence imposed by the district court is reversed, and the case is remanded with an instruction to re-sentence the Defendant in a manner consistent with the opinion herein.
. Westmoreland’s death certificate listed an incorrect Social Security number. Burrus also filed an annual report falsely detailing expenditures of benefits paid to Westmoreland.
. Burrus insists that the district court’s basis for its downward departure was not the age of her prior conviction. Instead, she points to the last paragraph of the above-cited segment of the sentencing colloquy, asserting that the downward departure was based on the district court’s consideration of the record. Burrus concludes that this means that the district court took into account the record as a whole in departing downward, and not sim*62ply the age of her prior conviction. First, a plain reading of the court's explanation does not support this analysis. Instead, as noted, the district court expressly eliminated the factors of addiction and relatedness of the prior offense as bases for departing downward, and endorsed the remoteness of time factor, by noting that Burrus's misdemeanor conviction had "occurred 15 years ago.” Second, even if Burrus is correct that the district court's decision was based on the record as a whole, this generic statement, without more, does not justify a downward departure. Moreover, as explained infra, the record fails to justify a downward departure.
. By the Government's count, Burras received, and fraudulently cashed, 156 checks, amounting to a loss to the Social Security Administration of approximately $85,194.