OPINION
MICHAEL, Circuit Judge:
Duane Lominac appeals from a sentence imposed for the violation of conditions of his supervised release. The district court revoked Lominac’s supervised release and sentenced him under 18 U.S.C. § 3583(e)(3) and (h) to a six-month term of imprisonment to be followed by a new thirty-month term of supervised release. Lominac contends that this sentence violates the prohibition against ex post facto laws because (1) § 3583(h) was enacted after he committed his original felonies and (2) this new section increases the punishment for his original crimes. Because we agree, we vacate the sentence and remand for resentencing.
I.
Lominac and an accomplice defrauded the American Express Travel Related Services Company out of $166,000 by using credit cards obtained under fictitious names. See American Express Travel Related Servs. Co. v. Lominac, 158 F.R.D. 376, 376-77 (E.D.Va.1994). Lominac pled guilty on July 6, 1989, to two counts of an indictment charging conspiracy to defraud, 18 U.S.C. § 371 (1988), and access device fraud, 18 U.S.C. § 1029(a)(2) (1988).1 He was sentenced to forty-one months of imprisonment and three years of supervised release for each offense, with the sentences to run concurrently. Lominac served his prison time, and on February 19,1993, he began the three-year term of supervised release.
On February 14, 1996, less than a week before Lominac would have completed his entire sentence, the district court issued a summons requiring him to appear and show cause why his supervised release should not be revoked. After holding an evidentiary hearing on March 26, 1996, the court found that Lominac had violated the terms of his [310]*310supervised release in several respects: (1) he submitted false monthly reports to the probation office by understating his income, by failing to note new employment, and by failing to report a change in his living arrangements, (2) he ignored his probation officer’s instruction to submit certain W-2 forms, (3) he failed to file a monthly report with the probation office for October 1995, and (4) he failed to inform his employer that he was a convicted felon.2 The court revoked Lominac’s release and sentenced him to serve six months in prison followed by thirty months of additional supervised release. Because this was Lominac’s second violation of supervised release,3 the court found “that it [wa]s proper to depart upward” from the three— to nine-month imprisonment range suggested in the 1991 Guidelines by adding a new term of supervised release to a six-month prison sentence. Cf. U.S. Sentencing Guidelines Manual § 7B1.4(a) (1991) .(nonbinding policy statement, adopted after Lominac’s conviction, recommending imprisonment range of three to nine months for grade C supervised release'violation by defendant with category I criminal history).
Lominac, who appeared at the hearing pro se, objected to this sentence, saying “I don’t think that I was originally convicted under the law you are sentencing me under---- I think that the subsection you are using ... to continue my supervised release ... was added on after I was originally convicted.” The district court took Lominae’s comment as an ex post facto challenge.
At the time Lominac committed his crimes, 18 U.S.C. § 3583(e) alone governed the sanction for violation of the conditions of super vised release. Once a violation was found, the district court (after considering specified factors) could under this subsection:
(1) terminate a term of supervised release and discharge the person released ...;
(2) extend a term of supervised release if less than the maximum authorized term [defined by 18 U.S.C. § 3583(b) ] was previously imposed, and ... modify, reduce, or enlarge the conditions of supervised release ...;
(3) revoke a term of supervised release, and require the person to serve in prison all or part of the term of supervised release without credit for the time previously served on postrelease supervision ..., except that a person whose term is revoked under this paragraph may not be required to serve more than 3 years in prison if the offense for which the person was convicted was a Class B felony, or more than 2 years in prison if the offense was a Class C or D felony; or
(4) order the person to remain at his place of residence during nonworking hours....
18 U.S.C. § 3583(e)(1)-(5) (1988) (including technical amendments added in 1990) (emphasis added).4 In United States v. Cooper, 962 F.2d 339 (4th Cir.1992), we rejected the argument that this subsection allows the imposition of both prison time and another term of supervised release. We found that “[s]ection 3583[ (e) ] is unambiguously written in the -disjunctive, presenting the court with four discrete choices when it elects to modify or revoke a term of supervised release.” Id. at 341. We added that “we must await congressional action, if any, for the addition of [311]*311flexibility to the provisions of section 3583(e)(3).” Id. at 342.
Congress acted on September 13, 1994, when it amended § 3583 by adding subsection (h). See Violent Crime Control and Law Enforcement Act of 1994, Pub.L. No. 103-322, § 110505(3), 108 Stat. 1796, 2017 (1994). The new subsection provides:
When a term of supervised release is revoked and the defendant is required to serve a term of imprisonment that is less than the maximum term of imprisonment authorized under subsection (e)(3), the court may include a requirement that the defendant be placed on a term of supervised release after imprisonment. The length of such a term of supervised release shall not exceed the term of supervised release authorized by statute for the offense that resulted in the original term of supervised release, less any term of imprisonment that was imposed upon revocation of supervised release.
18 U.S.C. § 3583(h) (1994). This subsection does not overrule our decision in Cooper, which limits a court to only one of the four options under § 3583(e). However, if the sentencing court chooses the imprisonment option, subsection (h) gives the court the additional authority to impose a new term of supervised release to follow imprisonment.
The district court rejected Lominac’s pro se argument that it was an ex post facto violation to use § 3583(h) to tack supervised release onto a prison term for violation of his release. In its analysis the district court first calculated the maximum punishment that Lominae could have received under § 3583(e), the only section applicable when he committed his underlying offenses. Because Lominae had been convicted of a Class C felony and a Class D felony, he could have been imprisoned for his release violations for not more than two years for each of these underlying felonies. See 18 U.S.C. § 3583(e)(3). Thus, the district- court determined that Lominac’s violations could have netted him a maximum penalty of four years in prison prior to the enactment of § 3583(h). The court concluded that “because [it had] imposed a six month term of confinement and a thirty month term of supervised release rather than imposing up to four years in prison, the [application of subsection (h) ] worked to Defendant’s advantage” and was not an ex post facto violation. Lominae now appeals with the assistance of counsel.
II.
Article I of the United States Constitution provides that Congress shall not pass any “ex post facto Law.” U.S. Const. art. I, § 9, cl. 3. “Although the Latin phrase ‘ex post facto’ literally encompasses any law passed ‘after the fact,’ it has long been recognized ... that the constitutional prohibition on ex post facto laws applies only to penal statutes which disadvantage the offender affected by them.” Collins v. Youngblood, 497 U.S. 37, 41, 110 S.Ct. 2715, 2718, 111 L.Ed.2d 30 (1990); accord Kansas v. Hendricks, — U.S. -, -, 117 S.Ct. 2072, 2086, 138 L.Ed.2d 501 (1997) (clause “has been interpreted to pertain exclusively to penal statutes”).
Lominae argues that the district court’s application of § 3583(h) retroactively increased the punishment for his original crimes. This argument implicates the two “central concerns” behind the Ex Post Facto Clause, that is, “ ‘the lack of fair notice and governmental restraint when the legislature increases punishment beyond what was prescribed when the crime was consummated.’ ” Lynce v. Mathis, 519 U.S. 433, -, 117 S.Ct. 891, 896, 137 L.Ed.2d 63 (1997) (quoting Weaver v. Graham, 450 U.S. 24, 30,101 S.Ct. 960, 965, 67 L.Ed.2d 17 (1981)); see also Hill v. Jackson, 64 F.3d 163, 167 (4th Cir.1995) (purposes of clause are to require “‘fair warning’ ” and to “ ‘restriet[ ] governmental power by restraining arbitrary and potentially vindictive legislation’ ” (quoting Weaver, 450 U.S. at 28-29, 101 S.Ct. at 963-65) (alteration in original)).
Our ex post facto analysis involves a two-step inquiry. “To fall within the ex post facto prohibition, a law must [1] be retrospective ... and [2] it ‘must disadvantage the offender affected by it’ by altering the definition of criminal conduct or increasing punishment for the crime.” Lynce, 519 U.S. at -, 117 S.Ct. at 896 (citations omitted); accord California Dep’t of Corrections v. [312]*312Morales, 514 U.S. 499, 504, 115 S.Ct. 1597, 1600-01, 131 L.Ed.2d 588 (1995); Collins, 497 U.S. at 43, 110 S.Ct. at 2719-20 (“Legislatures may not retroactively alter the definition of crimes or increase the punishment for criminal acts.”); see also Weaver, 450 U.S. at 29, 101 S.Ct. at 964. The two-step analysis follows.
A.
“A law is retrospective if it ‘changes the legal consequences of acts completed before its effective date.’ ” Miller v. Florida, 4482 U.S. 423, 430, 107 S.Ct. 2446, 2451, 96 L.Ed.2d 351 (1987) (quoting Weaver, 450 U.S. at 31, 101 S.Ct. at 965-66); see also Weaver, 450 U.S. at 28, 30, 101 S.Ct. at 963-64, 965 (retrospectivity determined in reference to time that “act to be punished occurred”); United States v. Parriett, 974 F.2d 523, 526 (4th Cir.1992) (same). Because § 3583(h) became effective after Lominac committed his felonious acts, the subsection plainly appears to be a retrospective law as applied to him. The government argues, however, that the application of § 3583(h) to Lominac is not retrospective because “revocation of supervised release is not ordered as punishment for an initial crime, but [instead is] punishment for failure to comply with the conditions of supervised release.” Government Br. at 5. Because Lominac violated the terms of his release after § 3583(h) was enacted', the government asserts that the sentence imposed does not change the legal consequences of acts completed before the effective date of the subsection. Thus, the government says, there is no violation of the prohibition against ex post facto laws. We disagree.
In Fender v. Thompson, 883 F.2d 303, 304 (4th Cir.1989), we were faced with an ex post facto challenge to a Virginia law providing that anyone “ ‘sentenced to life imprisonment who escapes from a correctional facility or from any person in -charge of his custody shall not be eligible for parole.’” Fender, who was serving a life sentence when the law was enacted, escaped from custody and subsequently pled guilty to one count of escape. After Fender received a three-year prison sentence for the independent crime- of escape, the Virginia Department of Corrections invoked the new law, issuing an order that Fender was no longer eligible for parole on his life sentence. On habeas review, we rejected the Commonwealth’s argument that the statute merely “enhanced punishment for the crime of ‘escape.’ ” Id. at 306. Although the Commonwealth “could have enacted a pure ‘recidivist’ statute [that] enhanced the penalty for [the crime of] escape” itself, it chose not to do that. Id. at 307 n. 3. Because we concluded that the punishment of parole ineligibility was not attributable to the crime of escape, we held that the effect of the statutory change was to increase retroactively the punishment for Fender’s prior crimes.
Later, in United, States v. Parriett, 974 F.2d 523, 525-27 (4th Cir.1992), we addressed an argument identical to the one before us today in the context of an ex post facto challenge to 18 U.S.C. § 3583(g). Effective since December 1988, § 3583(g) provided that a term of supervised release must be revoked when a defendant is found to be in possession of a controlled substance while on release. See 18 U.S.C. § 3583(g) (1988) (amended 1994); 974 F.2d at 525. Although Parriett had committed the crimes for which he was imprisoned and placed on supervised release before § 3583(g) was enacted, he violated his release by using drugs after the section had taken effect. See 974 F.2d at 525. The district court revoked his release for this violation under the authority of § 3583(g), and Parriett appealed to us claiming that this sentence violated the Ex Post Facto Clause. We agreed, holding that because the “revocation of Parriett’s supervised release was ... ordered as punishment for his initial crimes,” “the revision of the supervised release statute altered the legal consequences of Parriett’s original crime[s]” and thus could not be used to sentence him. See id. at 526. We explicitly rejected the contention that § 3583(g) served only to punish the act of violating his release (which occurred after § 3583(g) had taken effect), even though we acknowledged that “Parriett was ‘on notice’ of the consequences of drug possession,” id. at 527, when he committed the violation at issue.- See id: at 526-27. We held that “while Congress is free to alter the punishment for possession of controlled sub[313]*313stances [as an independent crime applicable to all persons], it cannot accomplish its goal by means of a ‘post hoc alteration of the punishment for an earlier offense.’ ” Id. at 526-27.
Our decision in Parriett completely forecloses the government’s argument in this ease. Because “punishment for violating the terms of supervised release is punishment for the original offense,” United States v. Woodrup, 86 F.3d 359, 361 (4th Cir.) (citing Parriett), cert. denied, — U.S. -, 117 S.Ct. 332, 136 L.Ed.2d 245 (1996), Lominac’s sentence under § 3583(h) for the violation of his release conditions cannot be characterized as punishment for new and independent infractions. Our own circuit precedent compels the conclusion that Lominac’s sentence under § 3583(h) retroactively increases the punishment for his original offenses. Moreover, our position is in accord with that of the Second, Third, Seventh, and Ninth Circuits. See United States v. Meeks, 25 F.3d 1117, 1119-24 (2d Cir.1994); United States v. Dozier, 119 F.3d 239, 241 (3d Cir.1997); United States v. Beals, 87 F.3d 854, 858-60 (7th Cir.1996), overruled in part on other grounds by United States v. Withers, 128 F.3d 1167, 1170-72 (7th Cir.1997); United States v. Collins, 118 F.3d 1394, 1397 (9th Cir.1997).5 Because the application of § 3583(h) to Lominae is retrospective, we now consider whether this application “disadvantaged” him.
B.
The focus in the second step of the inquiry “is not on whether a legislative change produces some ambiguous sort of ‘disadvantage,’ ... but on whether any .such change alters the definition of criminal conduct or increases the penalty by which a crime is punishable.” California Dep’t of Corrections v. Morales, 514 U.S. 499, 506 n. 3, 115 S.Ct. 1597, 1602 n. 3, 131 L.Ed.2d 588 (1995). There is no claim here that § 3583(h) changed the definition of any offense. Thus, Lominac’s sentence violates the Ex Post Facto Clause only if the use of § 3583(h) disadvantaged him by increasing the punishment he could have received for his crimes.
The government argues that the district court properly concluded that Lominae was not disadvantaged by an increase in punishment. The government says that Lominae could have received a four-year prison sentence under the old scheme, which would have restrained his liberty for .a period longer than the sentence he actually received (six months of imprisonment and thirty months of release). The government adds that § 3583(h) worked to Lominac’s advantage because it gave the district court the flexibility to fashion a sanction with a shorter jail term to be followed by a longer term of supervised release. This flexibility allowed the court to give Lominae a more lenient sentence that could be amplified later with additional prison or release time if he violated his release once again.
The government’s analysis, however, must be rejected. “[O]ne is not barred from challenging a change in the penal code on ex post facto grounds simply because the sentence he received under the new law was not more onerous than that which he might have received under the old.” Dobbert v. Florida, 432 U.S. 282, 300, 97 S.Ct. 2290, 2301-02, 53 L.Ed.2d 344 (1977); accord Miller v. Florida, 482 U.S. 423, 432, 107 S.Ct. 2446, 2452, 96 L.Ed.2d 351 (1987). Because “the Ex Post Facto Clause looks to the standard of punishment prescribed by the statute, rather than to the sentence actually imposed ... an increase in the possible penalty is ex post facto regardless of the length of the sentence actually imposed----” Lindsey v. Washington, 301 U.S. 397, 401, 57 S.Ct. 797, 799, 81 L.Ed. 1182 (1937) (citations omitted) (emphasis added); see also Morales, 514 U.S. at 510 n. 6, 115 S.Ct. at 1603 n. 6 (defendant need not “show[ ] that he would have been sentenced to a lesser term under [314]*314the measure or range of punishments in place under the previous statutory scheme”); Weaver v. Graham, 450 U.S. 24, 33, 101 S.Ct. 960, 966-67, 67 L.Ed.2d 17 (1981) (“The inquiry looks to the challenged provision, and not to any special circumstances that may mitigate its effect on the particular individual.”); United States v. Dozier, 119 F.3d 239, 243 (3d Cir.1997) (“[Section] 3583(h) violates the ex post facto prohibition if there is the potential that such application may even once result in a harsher sentence than previously authorized. The possibility that post 3583(h) sentences may frequently- be less onerous than otherwise is insufficient to redeem the statute.”). Cf. Dobbert, 432 U.S. at 294, 97 S.Ct. at 2298-99 (“We must compare the two statutory procedures in toto to determine if the new may be fairly characterized as more onerous.”). Thus, the government’s point that Lominac’s actual sentence was shorter than that possible under the old law and that the district court had the added flexibility to shorten the jail term and substitute time on supervised release does not answer the question before us.6
Instead, we must decide whether the overall effect of § 3583(h) disadvantaged Lominae by increasing the punishment he could have received for his crimes. As' a preliminary matter, we must determine whether § 3583(h) changed the law by allowing a court to sentence a defendant to both imprisonment and a new term of supervised release. In United States v. Cooper, 962 F.2d 339 (4th Cir.1992), we held that § 3583(e) did not allow a court to. impose both jail time and a new term of supervised release. It is therefore clear that § 3583(h) changed the law in this circuit.7
Before subsection (h) was enacted, this circuit read § 3583(e) to, allow a court, when sentencing for a violation of supervised release, to impose either imprisonment or extend the term of supervised release, but not both. See 18 U.S.C. § 3583(e)(2) & (3) (1988); Cooper, 962 F.2d at 341-42. If the court chose the option of imprisonment, the maximum term available would vary depending on the severity of the offense that resulted in the defendant’s original sentence of supervised release, and no credit was given for time previously served on supervised release. See 18 U.S.C. § 3583(e)(3) (1988). For Class A, B, C, D, and E felonies, the maximum prison term was (and is) five, three, two, two, and one year, respectively. See 18 U.S.C. § 3583(b) & (e)(3) (1988). On the other hand, if the court elected to increase the length of the term of supervised release under § 3583(e)(2), it could extend the total length up to five, five, three, three, or one year for Class A, B, C, D, or E felonies, respectively, if less than the maximum had already been imposed. See 18 U.S.C. § 3583(b) & (e)(2) (1988). Because this option only authorizes “extend[ing]” the term of supervised release, a defendant is [315]*315given credit for time already served on this term of release. See id. § 3583(e)(2). Both of these options are summarized in tabular form below.
Class of Felony
Length of prison term for violating condition of release, § 3583(b) &(e)
Length of total term of supervised release, § 3583(b) & (e)(3)
Up to 5 years Class A Up to 5 years
Up to 3 years Class B Up to 5 years
Up to 2 years Class C, D Up to 3 years
Up to 1 year Class E Up to 1 year
(and misdemeanors)
Accordingly, under § 3583(e) a person convicted of a Class C or D felony could have faced up to two years of prison or an extension of his supervised release term up to the three-year maximum .for each felony. Because Lominac had already served three years of concurrent supervised release on his Class C and D felonies by the time he was sentenced for violating his release, only the option of a prison term with a two-year cap (for each felony) would have been available to the court under the old scheme.
In contrast, the newly-enacted § 3583(h) empowers a court to do much more. In addition to allowing a court to sentence a defendant to virtually the same term of imprisonment as above, it provides that a new term of supervised release may also be imposed. See 18 U.S.C. § 3583(b), (e)(3) & (h) (1994). The length of this new supervised release term is capped at the maximum term of supervised release allowed by § 3583(b) for the original crime with credit given for any prison time imposed under § 3583(e)(3). See id. § 3583(h). Therefore, the maximum penalty for violating the terms of one’s release under § 3583(e)(3) and (h) is, for Class C and D felonies, two years (less one day) in prison and an additional year and a day of supervised release.8
This potential punishment is greater than that under § 3583(e) alone. While Lominac only faced two years of prison on each crime when § 3583(e) stood by itself, § 3583(h) exposed him to this same penalty (less one day) plus an additional year and a day of supervised release. Likewise, even if Lominac’s supervised release could have been extended under § 3583(e) alone, a three-year total term of release would clearly be less onerous than two new years (less one day) of prison and a new year and a day of release authorized by § 3583(h). See United States v. Dozier, 119 F.3d 239, 241-44 (3d Cir.1997) (reaching same conclusion and ruling that application of § 3583(h) violated Ex Post Facto Clause); United States v. Collins, 118 F.3d 1394, 1397 (9th Cir.1997) (same).9
[316]*316We therefore hold that the retrospective application of § 3583(h) disadvantaged Lominae by increasing the total amount of time that his liberty could be restrained in violation of the Ex Post Facto Clause.10
III.
The usual remedy for an ex post facto violation in sentencing is a remand for resentencing under the law in place at the time the defendant committed his crime. See Weaver v. Graham, 450 U.S. 24, 36 n. 22, 101 S.Ct. 960, 968 n. 22, 67 L.Ed.2d 17 (1981); see also United States v. Dozier, 119 F.3d 239, 244, 245 (3d Cir.1997) (remanding for resentencing and noting possibility of increase in sentence); United States v. McGee, 981 F.2d 271, 276 (7th Cir.1992) (remanding and noting that defendant had “won a pyrrhic victory” because of possibility of longer prison sentence on remand). But see United States v. Collins, 118 F.3d 1394, 1399 (9th Cir.1997) (vacating supervised release portion of sentence); United States v. Beals, 87 F.3d 854, 860 (7th Cir.1996) (remanding for district court to eliminate new term of supervised release), overruled in part on other grounds by United States v. Withers, 128 F.3d 1167, 1170-72 (7th Cir.1997). Lominac, however, took the position at oral argument that the proper remedy is an outright discharge. We disagree.
While North Carolina v. Pearce, 395 U.S. 711, 723-26, 89 S.Ct. 2072, 2079-81, 23 L.Ed.2d 656 (1969), modified in part, Alabama v. Smith, 490 U.S. 794, 798-802, 109 S.Ct. 2201, 2204-2206, 104 L.Ed.2d 865 (1989), and subsequent cases, see, e.g., Alabama v. Smith, supra; Texas v. McCullough, 475 U.S. 134, 137-44, 106 S.Ct. 976, 978-82, 89 L.Ed.2d 104 (1986); Chaffin v. Stynchcombe, 412 U.S. 17, 24-28, 93 S.Ct. 1977, 1981-83, 36 L.Ed.2d 714 (1973); United States v. Kincaid, 964 F.2d 325, 328 (4th [317]*317Cir.1992), make it clear that a district court cannot vindictively impose a higher sentence on remand, it is equally clear that a higher sentence may sometimes be justified. Thus, Pearce did not eliminate the risk that “a fresh sentence may be higher for some valid reason associated with the need for flexibility and discretion in the sentencing process.” Chaffin, 412 U.S. at 25, 93 S.Ct. at 1982; accord Alabama v. Smith, 490 U.S. at 799, 109 S.Ct. at 2204-05; see also Safrit v. Garrison, 623 F.2d 330, 332 (4th Cir.1980) (“a void or illegal sentence may be corrected, even though the correction may result in an increase in the sentence”).
When the district court sentenced Lominac to six months in prison and thirty months of supervised release for his release violation, the court said it was departing upward from the three to nine months of imprisonment recommended in the Guidelines. Had the court recognized that it lacked authority to impose the new term of supervised release, it might have validly concluded that a prison' term of longer than six months was appropriate.11 ■ For this reason, we will remand for resentencing.
‘ On remand, however, any prison time that Lominac receives under a resentence must' be reduced by the time he has already served for violating his release, that is, his six months in prison and the time he has served under the (new) unconstitutional term of supervised release. Under 18 U.S.C. § 3585(b)(1) (1994), the Attorney General, through the Bureau of Prisons, is required to credit Lominac' for the six months imprisonment served for his violation. See United States v. Wilson, 503 U.S. 329, 333, 112 S.Ct. 1351, 1353-54, 117 L.Ed.2d 593 (1992) (district court not authorized by § 3585(b) to compute credit for time spent in official detention at sentencing). Unlike prison time, though, time served on supervised release cannot be credited under this section because supervised release is not “official detention” which may be credited under § 3585(b). See 18 U.S.C. § 3585(b); United States v. Insley, 927 F.2d 185, 186-87 (4th Cir.1991); see also id. at 186 (noting that § 3583 replaced 18 U.S.C. § 3568 and construing “official detention” in § 3583(b) to have same meaning as “custody” in § 3568); Randall v. Whelan, 938 F.2d 522, 524-26 (4th Cir.1991) (rejecting argument that release conditions may be sufficiently restrictive so as to constitute “custody” and holding that release on conditional bond into residential drug treatment center is not “custody” under 18 U.S.C. § 3568). Because the Attorney General, under the statutory framework, cannot credit Lominac for time served on the unconstitutional term of supervised release, the district court on remand will give Lominac credit for that time against any new prison.sentence.
This result is mandated by the Double Jeopardy Clause. The Supreme Court has held that after a conviction is reversed, the Fifth Amendment’s guarantee against double jeopardy “absolutely requires that punishment already exacted must be fully ‘credited’ in imposing sentence upon a new conviction for the same offense.” Pearce, 395 U.S. at 718-19, 89 S.Ct. at 2077-78 (footnote omitted); see also Ohio v. Johnson, 467 U.S. 493, 499, 104 S.Ct. 2536, 2540-41, 81 L.Ed.2d 425 (1984); Wilson v. North Carolina, 438 F.2d 284, 286-87 (4th Cir.1971). Because the interest protected by the Double Jeopardy Clause’s prohibition against multiple punishments for the same offense “ ‘ensures] that the total punishment d[oes] not exceed that authorized by the legislature,”’ Jones v. Thomas, 491 U.S. 376, 381, 109 S.Ct. 2522, 2525-26, 105 L.Ed.2d 322 (1989), credit must be given not only when a defendant is resenteneed following a new conviction but also when he is resentenced after a successful challenge to his original ’sentence. See United States v. McMillen, 917 F.2d 773, 777 (3d Cir.1990) (credit for time served on probation must be “ ‘fully “credited” ’ ” on remand from government’s successful appeal of sentence). Otherwise, the cumulative punishment imposed on the defendant could exceed those restraints on his liberty that are authorized by the law.
[318]*318This applies for both imprisonment as well as for supervised release. Because supervised release is punishment, see Dozier, 119 F.3d at 242; United States v. Soto-Olivas, 44 F.3d 788, 790 (9th Cir.), cert. denied, 515 U.S. 1127, 115 S.Ct. 2289, 132 L.Ed.2d 290 (1995); Meeks, 25 F.3d at 1121-22, Pearce requires that it must be “fully ‘credited’” against Lominac’s new sentence. Any other holding would have the effect of nullifying the guarantee against ex post facto laws by allowing Lominac’s total punishment to exceed that originally authorized when he committed his crimes.12
Finally, in deciding to remand, we have considered whether Lominac has served all the time that he is legally required to serve. While the Supreme Court’s decision in In re Bradley, 318 U.S. 50, 63 S.Ct. 470, 87 L.Ed. 608 (1943), lends some support to the argument that he has, we believe Bradley is distinguishable. In Bradley the trial court was authorized to impose only imprisonment or a fine for the crime of contempt, but it erroneously sentenced the defendant to both six months in prison and a $500 fine. Before the sentencing court discovered its error and amended its sentence to eliminate the fine, the defendant paid the fine and was delivered into custody. The Supreme Court concluded that by paying the fine, the defendant “had complied with a portion of the sentence which could lawfully have been imposed.” Id. at 52, 63 S.Ct. at 471. Thus, because “one valid alternative provision of the original sentence ha[d] been satisfied,” id., the defendant was released from custody. See also United States ex rel. Kanawha Coal Operators Ass’n v. Miller, 540 F.2d 1213, 1214 (4th Cir.1976) (following Bradley).
Much like Bradley, Lominac was sentenced to two forms of punishment even though the applicable statute did not authorize the court to impose one of those forms. And because Lominac has served the six months in prison, he arguably has satisfied “one valid alternative provision of the original sentence” and, hence, should be released. However, as the Supreme Court explained in Jones v. Thomas, 491 U.S. 376, 384, 109 S.Ct. 2522, 2527, 105 L.Ed.2d 322 (1989), the “alternative sentences in Bradley ... were of a different type,” and it simply was not “possible to ‘credit’ a fine against time in prison.” While imprisonment and supervised release are clearly “different type[s]” of punishment, it is possible to credit Lominac’s time served on supervised release against any time to be served in prison. Unlike the monetary sanction of a fine, which cannot be converted into an equivalent temporal sanction, Lominac’s term of supervised release restrained his liberty for a known period of time that can be credited against any future sentence of imprisonment. Accordingly, Bradley does not bar resentencing.
Lominac’s sentence for violation of supervised release is vacated, and the ease is remanded for resentencing in conformity with this opinion.
VACATED AND REMANDED.