ORDER AND JUDGMENT *
MARY BECK BRISCOE, Circuit Judge. , • •After examining the briefs and appellate record, this panel has determined unahi*559mously that oral argument would not materially assist in the determination of this appeal. See Fed. R.App. P. 34(a)(2); 10th Cir. R. 34.1(G). The case is, therefore, submitted without oral argument.
Gregory Henderson, an Oklahoma inmate proceeding pro se, seeks a certificate of appealability (COA) in order to challenge the district court’s dismissal of his federal habeas corpus action seeking restoration of good time credits. Exercising jurisdiction pursuant to 28 U.S.C. § 1291, we grant Henderson’s application for COA, reverse the judgment of the district court, and remand the case to the district court with directions to conduct an evidentiary hearing, and such other proceedings as may be necessary, on Henderson’s claims.
I.
In 1988, the Oklahoma Department of Corrections (the Department), acting pursuant to a statutory directive, instituted a system of good time credits, whereby prisoners' could reduce their term of imprisonment for good conduct. See Okla. Stat. Ann. tit. 57, § 138. The statute authorized the Department to develop “a written policy and procedure whereby inmates shall be assigned to one (1) of four (4) class levels.... ” Id. § 138(B). In accordance with the statute, Level 1 inmates earned zero points per month of credit; Level 2 inmates earned 22 points; Level 3 inmates earned 33 points; and Level 4 inmates earned 44 points, each point being one day off the inmate’s prison time. The policy enacted by the Department provided for “an adjustment review committee/unit treatment team ... composed of not less than three staff members” to review an inmate’s earned good time credit level every three to four months and determine whether the inmate’s behavior warranted a promotion to a higher level.
Henderson began serving a thirty-year sentence for armed robbery on July 20, 1993, and is facing a consecutive thirty-year sentence, also for armed robbery, that is set to commence on January 3, 2021. On October 5, 1994, while incarcerated at an Oklahoma correctional center, Henderson assaulted a staff member. After a hearing, he was found to have committed the Class A offense of Battery Upon Staff with Injury, and received thirteen misconduct security points. Henderson sought review through the prison appeal process, but was unsuccessful.
The misconduct security points affected Henderson’s prison time in two ways. First, the misconduct security points were taken into account by the Department in determining his security level (security levels, as distinguished from earned good time credit levels, are used by the Department to determine which facility in which to place an inmate). Second, they were treated as active misconduct security points. Under the Department’s 1994 policies, active misconduct security points prevented an inmate from being promoted to Levels 3 or 4 for the purpose of earning good time credits, until such time as the active misconduct security points “expire[d]” or were “dropped.” R. Vol. 2, Attach. 9, OP 060103 § 111(C)(2). Notably, however, the record on appeal is devoid of any further information as to how or when, under the Department’s 1994 policies, active misconduct security points expired or were dropped.
On April 9, 1997, the Department revised its way of determining an inmate’s earned good time credit level. The revised instructions stated, in pertinent part: *560“There is no expiration on the current incarceration or within 10 years of the current incarceration for” Battery on Staff offenses. R. Vol. 2, Attach. 16 at 7, OP-060103(I)(B)(7) (1997). A related policy was also revised to allow for active misconduct security points to “be dropped after one year” “[f]or purposes of earned credit class assignment only,” if accompanied by “supporting documentation....” Id., OP-060213, Addendum 4, Major Changes (1997).
In July 1997, Henderson was promoted to Level 3 without an explicit statement by the Department that his active misconduct security points were dropped. Six months later, however, he was demoted for bad conduct. In March 1998, Henderson was again promoted to Level 3. Unable to maintain good behavior, Henderson was demoted five months later.
In March 2000, the Department again changed its policies. The revised policy required the “waiver” of active misconduct security points arising from offenses such as Henderson’s to be approved by “the facility head after ... one year....” R. Vol. II, Attach. 25 at 4-5, OP-060107(I)(D)(2) (2000). But in July 2000, Henderson was promoted to Level 3 without any supporting documentation and without approval by the facility head. He was, however, later demoted.
On October 8, 2001, an adjustment review committee concluded that Henderson was entitled to be promoted to Level 3, effective November 1, 2001. The promotion was ultimately rejected, however, on the grounds that Henderson’s Battery on Staff offense rendered him “ineligible” for promotion Level 3. R, Vol. 2, Attach. 35.
On October 9, 2001, Henderson filed a grievance claiming that the misconduct security points arising out of his Battery on Staff offense had expired after two years (i.e., on October 5, 1996), pursuant to the Department policies in effect at the time of that offense. As a result, he claimed, he was eligible for promotion to Level 3 in 1997 and beyond. In response, Henderson’s case manager wrote, “When you get [a Battery on Staff offense] it does not drop off for ten years. [Apparently someone dropped it off after 2 years. [OJbviously, someone else noticed it and had to add it back on.” R. Vol. 1, Dec. 05, 2001 Request to Staff. A few days later, the Department audited Henderson’s good time credits. Because Henderson’s file contained no waiver of his active misconduct security points, and because other computational errors were found to exist, the Department deducted 249 earned good time credits from his total credits.
After exhausting his administrative remedies, Henderson filed this action claiming, under the Department’s 1994 policy, that his misconduct security points either expired or were dropped. Henderson further claimed that the Department’s application of the 1997 and 2001 policies to his Battery on Staff offense -violated the Due Process and Ex Post Facto Clauses. The magistrate judge assigned to the case recommended that Henderson’s ex post facto claim be denied on the grounds that any changes in the Department’s policies were merely a change in Henderson’s custodial status, and not an increase in the measure of his punishment. The district court ultimately adopted the magistrate judge’s recommendation and dismissed Henderson’s petition, concluding the Department’s application of its amended policies to Henderson did not violate the prohibition against ex post facto laws.1 Thereafter, the district court denied Henderson’s ap*561plication for a COA. Henderson has since renewed his application for COA with this court.
II.
Issuance of a COA is a jurisdictional prerequisite to our review. Miller-El v. Cockrell, 537 U.S. 322, 336, 123 S.Ct. 1029, 154 L.Ed.2d 931 (2003). A COA may be issued “only if the applicant has made a substantial showing of the denial of a constitutional right.” 28 U.S.C. § 2253(c)(2). In order to make that showing, a prisoner must demonstrate “that reasonable jurists could debate whether (or, for that matter, agree that) the petition should have been resolved in a different manner or that the issues presented were adequate to deserve encouragement to proceed further.” Slack v. McDaniel, 529 U.S. 473, 484, 120 S.Ct. 1595,146 L.Ed.2d 542 (2000) (internal quotation marks omitted).
III.
Henderson contends the application of the Department’s 1997 and 2000 policies violated the Ex Post Facto Clause in two ways. First, he claims that under the Department’s 1994 policies, active misconduct security points expired after two years, but that the 1997 and 2000 policies eliminated that provision to his detriment. Second, he claims that under the Department’s 1994 policies, his active misconduct security points could be waived, but that the 1997 and 2000 policies deprived him of that opportunity. As a result, he claims the 1997 and 2000 policies have resulted in a substantial increase in his prison term.
The district court did not directly address these issues. Instead, citing our decision in Dyke v. Meachum, 785 F.2d 267 (10th Cir.1986), the district court held, as a matter of law, that the 1997 and 2000 policies did not implicate the Ex Post Facto Clause. For the reasons that follow, we conclude the district court erred in so holding.
Article I, § 10 of the Constitution prohibits the states from enacting an “ex post facto law.” “[T]he Clause is aimed at laws that retroactively alter the definition of crimes or increase the punishment for criminal acts.” California Dep’t of Corr. v. Morales, 514 U.S. 499, 504, 115 S.Ct. 1597, 131 L.Ed.2d 588 (1995) (internal quotation marks and citations omitted). “[T]he focus of the ex post facto inquiry is not on whether a legislative change produces some ambiguous sort of ‘disadvantage,’ nor ... on whether an amendment affects a prisoner’s ‘opportunity to take advantage of provisions for early release,’ but on whether any such change alters the definition of criminal conduct or increases the penalty by which a crime is punishable.” Id. at 506 n. 3, 115 S.Ct. 1597 (citation omitted; italics in original).
In Dyke, we held that the Ex Post Facto Clause was not implicated by the Department’s promulgation of a new classification system requiring that inmates serve twenty percent of their sentences in order to be eligible for reclassification to minimum security status, rather than the ten percent required under the former classification system. In so holding, we concluded that, “in the absence of any showing of a punitive intent, the Ex Post Facto Clause does not bar a prison from changing the regulations governing their internal classification of prisoners.” 785 F.2d at 268.
The district court’s reliance on Dyke in this ease was misplaced for at least two reasons. First, unlike the policies at issue here, the classification system at issue in Dyke did not lengthen prisoners’ incarceration. Rather, it changed their eligibility for placement within a different security level of the institution. Second, the policies at issue here, unlike the classification *562systems at issue in Dyke, were implemented by the Department pursuant to a statutory directive enacted by the Oklahoma Legislature. As a result, the policies at issue here can be fairly described as “legislative in nature,” and are thus subject to the ex post facto prohibition. Smith v. Scott, 223 F.3d 1191, 1193-94 (10th Cir.2000).
In our view, the Supreme Court’s decision in Garner v. Jones, 529 U.S. 244, 120 S.Ct. 1362, 146 L.Ed.2d 236 (2000), provides the controlling guidelines that we must follow in analyzing Henderson’s claims. In Gamer, the Court considered modified parole regulations that increased the length of time between parole reviews for prisoners. Similar to the case at hand, the policy at issue in Gamer invested a certain amount of discretion in prison officials. The Court noted “[t]he presence of discretion does not displace the protections of the Ex Post Facto Clause,” but it “is often a question of particular difficulty when the discretion vested ... is taken into account.” Id. at 250, 253, 120 S.Ct. 1362. The Court determined “[t]he question is a matter of degree,” with “[t]he controlling inquiry ... [being] whether retroactive application of the change ... created a sufficient risk of increasing the measure of punishment attached to the covered crimes.” Id. at 250, 120 S.Ct. 1362 (quotations omitted). Thus, in order to establish that a prison policy violates the Ex Post Facto Clause, an inmate must either demonstrate “the rule, ... by its own temis show[s] a significant risk” of increasing his punishment or present “evidence drawn from the rule’s practical implementation by the agency charged with exercising discretion, that its retroactive application will result in a longer period of incarceration than under the earlier rule.” Id. at 255, 120 S.Ct. 1362 (emphasis added).
Having reviewed the record on appeal in this case, it is apparent there is some confusion regarding how the Department actually applied its policies to Henderson’s 1994 Battery on Staff offense. Some of the statements by correction officials support the view that the Department relied on the 1997 policies in determining how that offense affected Henderson’s good time credits and the length of his sentence. Accordingly, we conclude it is necessary to remand this case for an evidentiary hearing at which the district court can determine how the Department applied the various regulations at issue to Henderson. See Miller v. Champion, 161 F.3d 1249, 1258-59 (10th Cir.1998) (remanding a § 2254 petition for an evidentiary hearing' to develop the factual record).
The request for a COA is GRANTED. The judgment of the district court is REVERSED and the case REMANDED to the district court with directions to conduct an evidentiary hearing, and such other proceedings as may be necessary, on Henderson’s claims for federal habeas relief.
This order and judgment is not binding precedent, except under the doctrines of law of the *559case, res judicata, and collateral estoppel. It may be cited, however, for its persuasive value consistent with Fed. R.App. P. 32.1 and 10th Cir. R. 32.1.
. Neither the district court nor the magistrate addressed Henderson’s due process claim.