OPINION
ERVIN, Chief Judge:Douglas Williams, Jr. appeals the district court’s denial of his petition for federal habeas corpus relief pursuant to 28 U.S.C. § 2254. The core of Williams’ arguments is that he did not have the mental capacity — because of organic brain damage and severe intoxication at the time of the offense — to have the requisite specific intent to be convicted of first-degree murder and sentenced to death. More specifically, he argues that he was not given the opportunity to prove that he lacked the requisite mental capacity — because of either ineffective assistance of counsel, or some other violation of his rights either at trial, at sentencing, on appeal, or in the post-conviction proceedings.
After this appeal was argued, the United States Supreme Court declared unconstitutional the North Carolina jury instruction requiring unanimity among the jurors before they could consider mitigating circumstances in death penalty sentencing deliberations. McKoy v. North Carolina, 494 U.S. 433, 110 S.Ct. 1227, 108 L.Ed.2d 369 (1990). This jury instruction was given at Williams’ trial. We affirm the district court’s holding that the trial court did not commit constitutional error at the guilt phase of the trial; therefore, we do not disturb Williams’ conviction. We further hold that Williams may receive the benefit of the rule set out in McKoy; therefore, we vacate his sentence and remand to the district court.
I
On August 2, 1981, Williams was arrested and charged with the murder of Adah Herndon Dawson. A detailed description of the crime and the investigation leading to his arrest is set forth in State v. Williams, 308 N.C. 47, 301 S.E.2d 335, 339-341 (1983). Williams pled not guilty. The jury found Williams guilty of first-degree murder. It concluded that he had murdered Dawson during the perpetration of a first-degree burglary, as well as during the perpetration of a sex offense, and that the murder was committed with malice and premeditation and deliberation. After the sentencing hearing, the jury imposed the death penalty which was ordered by the trial court judge.
On appeal, the conviction was upheld by the North Carolina Supreme Court on April 5, 1983. Williams, 308 N.C. 47, 301 S.E.2d 335 (1983). The United States Supreme Court denied Williams’ Petition for Writ of Certiorari on October 3, 1983. Williams v. North Carolina, 464 U.S. 865, 104 S.Ct. 202, 78 L.Ed.2d 177 (1983). Williams’ Petition for Rehearing was denied on November 28, 1983. Williams v. North Carolina, 464 U.S. 1004, 104 S.Ct. 518, 78 L.Ed.2d 704 (1983).
On May 7, 1984, Williams filed a Motion for Appropriate Relief, a state post-conviction procedure, pursuant to N.C.G.S. § 15A-1411 et seq. Twenty-one claims for relief were alleged in the motion, including ineffective assistance of counsel at trial and on appeal. During these proceedings, Williams’ new counsel filed numerous motions, all of which were denied by the state court judge.1 The court did order that an evidentiary hearing be held on one claim— ineffective assistance of counsel at trial— and that Williams’ remaining claims would “be heard on the record before the court and oral arguments.”
The evidentiary hearing was held on June 4-5, 1985, after which the state court judge entered an order denying Williams’ post-conviction relief. The North Carolina Supreme Court denied Williams’ petition for discretionary review.
On October 13, 1987, Williams filed a Petition for Writ of Habeas Corpus pursuant to 28 U.S.C. § 2254 in the United States District Court for the Eastern District of *451North Carolina. The petition contained twenty-four claims for relief. The judge denied the petition without oral argument on September 13, 1988. From this denial of habeas corpus relief, Williams now appeals.
II
Williams raises three issues arising from the guilt phase of his trial. First, he contends that the imposition of the death penalty upon a mildly mentally retarded defendant violates the constitution. Second, he alleges that he did not receive effective assistance of counsel. Third, he asserts that the evidence was insufficient to support the jury’s verdict finding Williams guilty of first-degree murder. We find no merit in any of these arguments.
A
The Supreme Court in Penry v. Lynaugh, 492 U.S. 302, 109 S.Ct. 2934, 106 L.Ed.2d 256 (1989), held that the execution of a mentally retarded defendant convicted of a capital offense is not categorically prohibited by the Eighth Amendment. This precedent forecloses this issue.
B
The standard by which to judge claims alleging ineffective assistance of counsel is set forth in Strickland v. Washington, 466 U.S. 668, 104 S.Ct. 2052, 80 L.Ed.2d 674 (1984). The standard in Strickland consists of two prongs. First, the court must inquire into the competence of the legal assistance in question. “The proper measure of attorney performance remains simply reasonableness under prevailing professional norms.” Id. at 688, 104 S.Ct. at 2065. In this regard, an attorney’s conduct is to be accorded a great deal of deference, and a reviewing court should avoid second-guessing the attorney with the benefit of hindsight. The second prong of the test involves assessing whether, given that counsel’s assistance was constitutionally deficient, this fact had a reasonable probability of affecting the outcome. In other words, the petitioner “must show that there is a reasonable probability that, but for counsel’s unprofessional errors, the result of the proceeding- would have been different. A reasonable probability is a probability sufficient to undermine confidence in the outcome.” Id. at 694, 104 S.Ct. at 2068.
Williams specifically argues three major errors in his representation. First, that his attorney should have sought out available witnesses who saw Williams staggering drunk near the time of the offense. Second, that he should have discovered readily available mental health experts who diagnosed Williams as mentally retarded and brain damaged at the time of the offense and who would testify that Williams’ mental condition satisfied, the test for statutory and nonstatutory mitigation. Third, the attorney unreasonably introduced Williams’ nine prior convictions during his capital sentencing argument, even though the State could not have introduced the convictions.
After careful review of the record, we agree that Williams’ attorney could have perhaps investigated the facts of the case more thoroughly and with more diligence. However, we cannot conclude that his conduct was unreasonable without engaging in excessive second-guessing, which we refuse to do. • Moreover, in light of the evidence, we believe that the government has carried its burden of showing beyond a reasonable doubt that the verdict would not have been different even if Williams’ counsel had been more diligent or had used different trial tactics. See Smith v. United States, - U.S. -, 112 S.Ct. 667, 116 L.Ed.2d 758 (1991) (denial of certiorari) (Blackmun, J., dissenting, and Stevens, J., dissenting).
C
We find the evidence to be sufficient to support the jury’s verdict. In his confession, Williams stated that when he entered the Dawson house, he was looking for a place to sleep and thought that the house was deserted. Once inside, he was surprised by Dawson, who threw salt in his face. While in a state of alcohol and drug *452intoxication, he struck her with a stick he picked up on the porch, knocking her down. After rummaging through the house, he went back into the kitchen and forced a mop handle into her vagina. The medical examiner found that Mrs. Dawson had severe cuts on her neck, face, scalp, ears, vagina, and rectum. She also had fractures of the skull, pubic bones, hip bones, and some facial bones.
■Williams now argues that his confession contains no evidence of any deliberation or premeditation to kill Dawson. Furthermore, he claims he had no “intent to commit larceny” when he entered the house and thus could not be convicted of felony-murder with the underlying felony being burglary. In addition, he contends that the murder was not “in perpetration of” a sex offense.
As the district court found, these arguments have little merit. We find particularly weak the argument that this murder was not committed “in perpetration of” a sex offense. The nexus between the sex act and the murder that Williams claims is required for felony-murder is much too restrictive and burdensome. See State v. Williams, 308 N.C. at 67, 301 S.E.2d at 348; State v. Powell, 299 N.C. 95, 261 S.E.2d 114 (1980).
Ill
In his sentencing instructions, the judge listed the following considerations as possible mitigating factors: Williams' age; his mental problems and deficiencies; and his condition the night of the murder (allegedly intoxicated and under the influence of drugs).
In the sentencing proceedings, the jury was asked to answer unanimously four questions: (1) whether there were any aggravating factors (proved by the State); (2) whether there were any mitigating factors (proved by Williams); (3) whether the aggravating circumstances outweighed the mitigating circumstances; and (4) whether the aggravating circumstances were sufficiently substantial to justify the imposition of the death penalty. At the time of Williams' trial, a North Carolina capital sentencing jury was required to “unanimously find that a mitigating circumstance existed] before it [could] be considered for the purpose of sentencing.” State v. Kirkley, 308 N.C. 196, 218, 302 S.E.2d 144, 157 (1983).
This unanimity requirement was struck down by the United States Supreme Court in McKoy v. North Carolina, 494 U.S. 433, 110 S.Ct. 1227, 108 L.Ed.2d 369 (1990). Following its reasoning in Mills v. Maryland, 486 U.S. 367, 108 S.Ct. 1860, 100 L.Ed.2d 384 (1988), the Court held that such a sentencing scheme “created ‘a substantial probability that reasonable jurors ... well may have thought they were precluded from considering any mitigating evidence unless all 12 jurors agreed on the existence of a particular [mitigating] circumstance.’ ” McKoy, 110 S.Ct. at 1230 (quoting Mills, 486 U.S. at 384, 108 S.Ct. at 1870). The law is well established in this area that “ ‘the sentencer [may] not be precluded from considering, as a mitigating factor, any aspect of a defendant’s character or record and any of the circumstances of the offense that the defendant proffers as a basis for a sentence less than death.’ ” Eddings v. Oklahoma, 455 U.S. 104, 110, 102 S.Ct. 869, 874, 71 L.Ed.2d 1 (1982) (quoting Lockett v. Ohio, 438 U.S. 586, 604, 98 S.Ct. 2954, 2964, 57 L.Ed.2d 973 (1978)). Under McKoy, the unanimity requirement given to the jury at Williams’ sentencing proceedings did limit the individual juror’s consideration of mitigating circumstances and was, therefore, unconstitutional.
Since the United States Supreme Court’s McKoy opinion, the North Carolina Supreme Court has held that that decision did not completely invalidate the North Carolina death penalty statute. See State v. McKoy, 327 N.C. 31, 394 S.E.2d 426 (1990) (“McKoy II”). Consequently, Williams is not entitled to have his sentence automatically reduced to life imprisonment. As a result, we must determine whether Williams can benefit from the rules set out by the Supreme Court in McKoy and its predecessor Mills.
*453A
Williams’ conviction became final in 1983,2 State v. Williams, 308 N.C. 47, 301 S.E.2d 335, cert. denied, 464 U.S. 865, 104 S.Ct. 202, 78 L.Ed.2d 177 reh’g denied, 464 U.S. 1004, 104 S.Ct. 518, 78 L.Ed.2d 704 (1983), before the decisions in the Mills and McKoy cases were handed down. Therefore, under the Supreme Court’s holdings in Teague v. Lane, 489 U.S. 288, 109 S.Ct. 1060, 103 L.Ed.2d 334 (1989), and Penry v. Lynaugh, 492 U.S. 302, 109 S.Ct. 2934, 106 L.Ed.2d 256 (1989), if the decisions in Mills and McKoy are deemed to be “new rules,” then Williams cannot receive the benefit of those rules even though the jury instructions were identical to those struck down in McKoy.
In Teague, the Supreme Court adopted Justice Harlan’s general rule on nonretroactivity for cases on collateral review, which he set out in Mackey v. United States, 401 U.S. 667, 675, 91 S.Ct. 1160, 28 L.Ed.2d 404 (1971) (separate opinion). The general rule is that “new rules” should not be applied retroactively to cases on collateral review. Teague, 489 U.S. at 305, 109 S.Ct. at 1072. There are two exceptions to the general rule. The first is that “a new rule should be applied retroactively if it places ‘certain kinds of primary, private individual conduct beyond the power of the criminal law-making authority to proscribe.’ ” Teague, 489 U.S. at 307, 109 S.Ct. at 1073 (quoting Mackey, 401 U.S. at 692, 91 S.Ct. at 1180 (separate opinion)). The second exception is that a new rule should be applied retroactively if it would “alter our understanding of the bedrock procedural elements that must be found to vitiate the fairness of a particular conviction” and “without which the likelihood of an accurate conviction is seriously diminished.” Id. 489 U.S. at 311-313, 109 S.Ct. at 1075-1077. In Penry v. Lynaugh, 492 U.S. 302, 109 S.Ct. 2934, 106 L.Ed.2d 256 (1989), the Court held that the “new rule” limitation on the exercise of habeas corpus jurisdiction applies in both capital and non-capital cases.
B
The Teague Court defined a new rule as follows:
In general, ... a case announces a new rule when it breaks new ground or imposes a new obligation on the states or the Federal Government. To put it differently, a case announces a new rule if the result was not dictated by precedent existing at the time the defendant’s conviction became final.
Teague, 489 U.S. at 301, 109 S.Ct. at 1070. Normally, because Williams seeks the benefit of the rules in Mills and McKoy, we would first have to determine whether those rules constitute new rules under Teague. However, in this case, we find that even if Mills and McKoy are new rules, one of the exceptions to the nonre-troactivity rule applies. Therefore, we will not address whether Mills and McKoy are new rules at this time.3
C
The first exception is that new rules will apply retroactively'if they place “certain kinds of primary, private individual conduct beyond the power of the criminal law-making authority to proscribe.” Teague, 489 U.S. at 307, 109 S.Ct. at 1073. The proscribed conduct in Williams’ case is capital *454murder, and the prosecution of capital murder is not prohibited by Mills or McKoy. See Butler v. McKellar, 494 U.S. 407, 110 S.Ct. 1212, 1217, 108 L.Ed.2d 347 (1990) (noting that the prosecution of capital murder was not prohibited by the new rule in Arizona v. Roberson, 486 U.S. 675, 108 S.Ct. 2093, 100 L.Ed.2d 704 (1988)). Therefore, the first exception does not apply in this case.
The second exception, however, does apply to this case. “The precise contours of this exception may be difficult to discern, ...” Saffle v. Parks, 494 U.S. 484, 110 S.Ct. 1257, 1264, 108 L.Ed.2d 415 (1990). In a recent case, the Supreme Court further explained the scope of the second Teague exception as follows:
In Teague, we modified Justice Harlan’s test to combine the accuracy element of the Desist test with the Mackey limitation of the exception to watershed rules of fundamental fairness. It is thus not enough under Teague to say that a new rule is aimed at improving the accuracy of the trial. More is required. A rule that qualifies under this exception must not only improve accuracy, but also ‘alter our understanding of the bedrock procedural elements’ essential to the fairness of a proceeding.
Sawyer v. Smith, 497 U.S. 227, 110 S.Ct. 2822, 2831, 111 L.Ed.2d 193 (1990) (quoting Teague, 489 U.S. at 311, 109 S.Ct. at 1076).
One rule which is repeatedly cited as an example of a rule falling within the second exception is Gideon v. Wainwright, 372 U.S. 335, 83 S.Ct. 792, 9 L.Ed.2d 799, which held that a defendant has the right to be represented by counsel in all criminal trials for serious offenses. Saffle, 110 S.Ct. at 1264. New rules which lack the “primacy and centrality of the rule adopted in Gideon” do not fall within the second Teague exception. See id.
An example of a new rule which lacked the “primacy and centrality” of Gideon was the rule adopted in Caldwell v. Mississippi, 472 U.S. 320, 105 S.Ct. 2633, 86 L.Ed.2d 231 (1989). In Sawyer v. Smith, the Supreme Court held that Caldwell was a new rule under Teague and did not fit either of the two exceptions. Sawyer, 110 S.Ct. 2822. Caldwell held that the Eighth Amendment prohibits the imposition of the death penalty by a sentencer that has been led to believe that the responsibility for determining the appropriateness of the defendant’s capital punishment lies elsewhere. Caldwell, 472 U.S. at 328-29, 105 S.Ct. at 2639-40. Sawyer argued that the second Teague exception “should be read to include new rules of capital sentencing that ‘preserve the accuracy and fairness of capital sentencing judgments.”' Sawyer, 110 S.Ct. at 2831. The Supreme Court disagreed because such a test disregarded the additional requirement that the rule must also “alter our understanding of the bedrock procedural elements ” essential to the fairness of a proceeding. Sawyer, 110 S.Ct. at 2831. The Court then found that Caldwell failed to meet this latter requirement.
Sawyer is important because it shows that the rules in Mills and McKoy easily meet the first requirement of the second Teague exception that the new rule be aimed at improving the accuracy of the trial. In Sawyer, the Court stated:
All of our Eighth Amendment jurisprudence concerning capital sentencing is directed toward the enhancement of reliability and accuracy in some sense.
Sawyer, 110 S.Ct. at 2831. In fact, it was because every Eighth Amendment case concerning capital punishment does meet the first requirement of the second Teague exception that the Court refused to adopt Sawyer’s interpretation of the exception. The Court focused on the fact that Caldwell did not meet the second requirement, explaining:
The Caldwell rule was designed as an enhancement of the accuracy of capital sentencing, a protection of systemic value for state and federal courts charged with reviewing capital proceedings. But given that it was added to an existing guarantee of due process protection against fundamental unfairness, we cannot say this systemic rule enhancing reliability is an “absolute prerequisite to *455fundamental fairness, 489 U.S., at 314, 109 S.Ct., at 1077, of the type that may come within Teague’s second exception.
Sawyer, 110 S.Ct. at 2832. Because the Caldwell rule did not meet the “bedrock procedural elements” requirement, the rule did not fall within the second Teague exception, and Sawyer could not benefit from the new rule. Sawyer indicates that the rules adopted in Mills and McKoy meet the first requirement of the second Teague exception in that they are aimed at increasing the accuracy of capital sentencing. See Sawyer, 110 S.Ct. at 2831; see also Woodson v. North Carolina, 428 U.S. 280, 305, 96 S.Ct. 2978, 2991, 49 L.Ed.2d 944 (1976) (noting that because of the difference between a sentence of death and a sentence of life imprisonment, “there is a corresponding need for reliability in the determination that déath is the appropriate punishment in a specific case”). What we must decide is whether the Mills and McKoy rules meet the second requirement of the second Teague exception. Justice Harlan explained this second requirement in Mackey v. United States:
[ I]n some situations it might be that time and growth in social capacity, as well as judicial perceptions of what we can right-, ly demand of the adjudicatory process, will properly alter our understanding of the bedrock procedural elements that ' must be found to vitiate the fairness of a particular conviction.
401 U.S. 667, 693, 91 S.Ct. 1160, 1180, 28 L.Ed.2d 404 (1971). The rules in Mills and McKoy fit the above description.
“It is well established that the Eighth Amendment draws much of its meaning from ‘the evolving standards of decency that mark the progress of a maturing society.’ ” Woodson v. North Carolina, 428 U.S. 280, 301, 96 S.Ct. 2978, 2989, 49 L.Ed.2d 944 (1976) (quoting Trop v. Dulles, 356 U.S. 86, 101, 78 S.Ct. 590, 598, 2 L.Ed.2d 630 (1958) (plurality opinion)). In addition, the sentence of death is a punishment different in kind, rather than different in degree, from all other sanctions. See id. 428 U.S. at 303-04, 96 S.Ct. at 2990-91; Furman v. Georgia, 408 U.S. 238, 309-10, 92 S.Ct. 2726, 2762-63, 33 L.Ed.2d 346 (1972) (Stewart, J., concurring).
The Supreme Court has repeatedly held that the imposition of death requires that the sentencing be individualized. See Sumner v. Shuman, 483 U.S. 66, 75, 107 S.Ct. 2716, 2722, 97 L.Ed.2d 56 (1987); Woodson, 428 U.S. at 304, 96 S.Ct. at 2991. In Woodson, the court stated:
While the prevailing practice of individualized sentencing determinations generally reflects simply enlightened policy rather than a constitutional imperative, we believe that in capital cases the fundamental respect for humanity underlying the Eighth Amendment, see Trop v. Dulles, 356 U.S., at 100 [78 S.Ct. at 597] (plurality opinion), requires consideration of the character and record of the individual offender and the circumstances of the particular offense as a constitutionally indispensable part of the process of inflicting the penalty of death.
428 U.S. at 304, 96 S.Ct. at 2991. See also Saffle, supra, 110 S.Ct. at 1270 (Brennan, J., dissenting) (“The right to an individualized sentencing determination is perhaps the most fundamental right recognized at the capital sentencing hearing.”).
In Sumner v. Shuman, 483 U.S. 66, 107 S.Ct. 2716, 97 L.Ed.2d 56 (1987), the Court traced the history of capital punishment cases. There, the Court explained that the “constitutional mandate of individualized determinations in capital-sentencing proceedings” caused the court to invalidate death sentences where the sentencer did not consider mitigating factors. Id. at 75-76, 107 S.Ct. at 2722. The Court explained that the Eighth Amendment requires that mitigating evidence be presented to the sentencer and further requires the sentencer to listen to that evidence. Id. at 76, 107 S.Ct. at 2722.
The discussions in Woodson and Sumner support the view that a rule striking down a unanimity requirement for mitigating circumstances is “implicit in the concept of ordered liberty,” Teague, 489 U.S. at 307, 109 S.Ct. at 1075 (quoting Palko v. Connecticut, 302 U.S. 319, 325, 58 S.Ct. 149, 152, 82 L.Ed. 288 (1937) (Cardozo, J.)). The *456language of Mills further enforces this view.
In Mills, the Court addressed the possibility that under Maryland’s sentencing scheme, one holdout juror could prevent the other eleven jurors from considering mitigating evidence. Mills, 486 U.S. at 374, 108 S.Ct. at 1865. The Court rejected this scheme as arbitrary:
Although jury discretion must be guided appropriately by objective standards, it would certainly be the height of arbitrariness to allow or require the imposition of the death penalty under the circumstances [where one holdout juror prevents the consideration of mitigating evidence].
Id. at 374, 108 S.Ct. at 1865 (emphasis added) (citations omitted).
In McKoy, Justice Kennedy further explored the arbitrariness of the unanimity requirement. He stated that the application of the death penalty on the basis of a single juror’s vote
... represents imposition of capital punishment through a system that can be described as arbitrary or capricious. The Court in Mills described such a result as the “height of arbitrariness.” Given this description, it is apparent that the result in Mills fits within our line of eases forbidding the imposition of capital punishment on the basis of “caprice,” in “an arbitrary and unpredictable fashion,” or through “arbitrary” or “freakish" means.
McKoy, 110 S.Ct. at 1239 (Kennedy, J., concurring) (citations omitted).
We find that the rules set out in Mills and McKoy are “bedrock procedural elements” and are “implicit in ordered liberty.” The procedures they struck down have been described as “arbitrary” and “capricious.” Those procedures did not provide for the “fundamental respect for humanity underlying the Eighth Amendment.” Woodson, 428 U.S. at 304, 96 S.Ct. at 2991. Given the history of the Eighth Amendment jurisprudence and the constitutional requirement of individualized sen-fences, we believe that a rule striking down an arbitrary unanimity requirement has the same “primacy and centrality” of Gideon. Therefore, we hold that the Mills and McKoy rules fall within the second Teague exception and should be applied retroactively. Applying Mills and McKoy to Williams’ case, we find that the jury instructions in this case were constitutionally defective. At sentencing, the court required the jury to unanimously find the existence of mitigating circumstances.4 This unanimity requirement was identical to the unanimity requirement struck down as unconstitutional by the Supreme Court in McKoy. See McKoy, 110 S.Ct. at 1230. Cf. Maynard v. Dixon, 943 F.2d 407, 419-20 (4th Cir.1991). Therefore, under McKoy, the jury instructions in this case were unconstitutional. As a result, we must vacate the sentence of death imposed upon Williams as unconstitutional due to the defective instructions. Accordingly, we vacate Williams’ sentence and remand this case to the district court.
IV
There is, in our view, another reason for vacating Williams’ sentence which is independent of the reason set forth in part III. This case also presents the question of whether a state’s failure to raise Teague in the court below waives it as a defense. Our reading of the Court’s statements on the role of Teague, our consideration of the holdings of our sister circuits, and our recent decision in Maynard, supra, lead us to conclude that Teague's retroactivity analysis is not jurisdictional in nature and is an affirmative defense that must be asserted below or else be waived.
The State, seizing on language from Pen-ry, contends that this court must determine “as a threshold matter,” 492 U.S. at 313, 109 S.Ct. at 2944, whether Williams’ claim for application of Mills/McKoy is barred by the prohibition against retroactive application of “new rules.” In Teague the Court did state that a habeas court must *457consider the retroactivity component, i.e., Is a “new rule” being invoked?, before assessing whether the facts of a case meet the rule. However, subsequent cases have shown that this is a matter of logic and not of jurisprudence. Which is to say that if the question is properly presented to a court, then a court should consider first whether a rule can be applied retroactively before deciding whether the case under review meets the rule. That this formulation was not of jurisprudential consequence was made clear by Chief Justice Rehnquist in Collins v. Youngblood: “Although the Teague rule is grounded in important considerations of federal-state relations, we think it is not ‘jurisdictional’ in the sense that this Court, despite a limited grant of certiorari, must raise and decide the issue sua sponte.” 497 U.S. 37, 110 S.Ct. 2715, 2718, 111 L.Ed.2d 30 (1990) (emphasis in original).
In this case, the chronology of the chain of events is very important. The Mills decision was handed down on June 6, 1988. Mills, 486 U.S. 367, 108 S.Ct. 1860, 100 L.Ed.2d 384. Thereafter, the district court entered its order denying Williams’ habeas relief on September 13, 1988.5 (JA Vol I, Tab E.) Teague, was decided five months later on February 22, 1989. Teague, 489 U.S. 288, 109 S.Ct. 1060, 103 L.Ed.2d 334. The first oral argument before this court on appeal was heard on November 2, 1989. The McKoy decision was decided four months later on March 12, 1990. Despite the fact that Williams raised the Mills issue before the district court, the State admittedly did not raise the retroactivity issue until after the McKoy decision was rendered.6 At that time and well after the first oral argument had been held before this court, the State cited this court to additional authority pursuant to Fed. R.App.P. 28(j) and raised the retroactivity issue for the first time. Because of the State’s failure to raise the issue until after the district court’s decision and this court’s first hearing on this appeal, we are confronted with the question of whether the State’s failure amounts to a waiver of the issue.
In Hanrahan v. Greer, the Seventh Circuit held that the court need not go into the “new rule” analysis because the State did not preserve an objection to the “retroactive application” of the rule at issue. 896 F.2d 241, 245. (1990) Judge Easterbrook noted that the Court had raised the retroac-tivity question on its own in Teague, but observed that the Court had the practice of applying a novel constitutional rule to the case establishing the rule. More powerfully, he concluded that the State “had missed the boat” by failing to raise the retroactivity issue. Id.
The Seventh Circuit was not swayed by the State’s argument that Teague had not yet been decided at the time the parties were arguing about the impact of the rule set out in Cruz v. New York, 481 U.S. 186, 107 S.Ct. 1714, 95 L.Ed.2d 162 (1987):
[ T]he state did not preserve an objection to the retroactive application of Cruz. After Cruz came down, the district judge called for briefs on its effects. The state tackled the merits without suggesting that Cruz should not be applied to [the defendant’s] case. Although it filed this response before the Court decided Teag-ue, that is neither explanation nor excuse.
Disputes about the retroactive application of constitutional decisions have pervaded criminal procedure over the last 25 years. Teague adopted the position Justice Harlan espoused in Mackey v. United States, 401 U.S. 667, 675, 91 S.Ct. 1160, 1164, 28 L.Ed.2d 404 (1971) (dissenting opinion), which in recent years had gathered the support of a majority of the Justices — though never before Teague in the same case on a collateral *458attack. (Griffith v. Kentucky, 479 U.S. 314, 107 S.Ct. 708, 93 L.Ed.2d 649 (1987), adopted Justice Harlan’s position for cases on direct appeal.) Prosecutors had been pumping for Justice Harlan’s position for years. Not phrasing an objection to retroactivity in the precise terms the Court adopted in Teague is one thing; not phrasing any objection to retroactivity is another.
Hanrahan, 896 F.2d at 245 (emphasis in original). The Seventh Circuit held that the State’s failure to raise the retroactivity issue constituted a waiver of the issue. Id.
Other circuits have gone the other way. In Hopkinson v. Shillinger, 888 F.2d 1286 (10th Cir.1989) (en banc), the Tenth Circuit held that “the non-retroactivity defense is not waived, and should be considered.” Id. at 1288. In reaching this conclusion the court noted that “the non-retroactivity defense ... was not previously available to the state” because Teague was decided after the district court entered judgment. For that reason, and because the court saw the scope of the writ of habeas corpus as implicated, the court held that it must raise “the nonretroactivity defense” sua sponte. Id. Similarly, in Smith v. Black, 904 F.2d 950, 981 n. 12 (5th Cir.1990), a panel for the Fifth Circuit found that though the circuits have split, “the better choice is to reach the Teague issue” whenever it is raised by the State.
The crux of the cases holding that re-troactivity analysis cannot be waived is that courts must be able to take up the issue sua sponte because, after all, that is what the Supreme Court itself did in Teag-ue, See id.; Hopkinson, 888 F.2d at 1288. We are unpersuaded by this reasoning. As Judge Easterbrook points out in Hanra-han, “there had been a practice of applying a novel constitutional rule to the case establishing the rule and asking the retroac-tivity question later. Teague changed that practice.... [Thus,] it is understandable that the state did not object to the application of the rule to Teague himself, although the state had objected to the retroactive application to Teague of Batson v. Kentucky, 476 U.S. 79 [106 S.Ct. 1712, 90 L.Ed.2d 69] (1986).” 896 F.2d at 245. Moreover, since Teague does not represent a change in practice by the Court, it cannot seriously be contended that the Court’s reaching the question in Teague means that all courts must reach the same question — that view denies the role the Court plays in our system. And this view of retroactivity analysis is confirmed by the Court’s holding in Collins v. Youngblood, in which it declared that the Teague rule “is not ‘jurisdictional.’ ”
Since the Teague rule is not jurisdictional, in the sense that a court must address it sua sponte if not raised, see Collins, 110 S.Ct. at 2718, then we confront the question whether a state’s failure to raise it below amounts to waiver.
We begin with the general rule that claims not adjudicated below, and in particular defenses that have not been raised in a pleading, by motion, or at trial, normally will be considered waived and cannot be heard for the first time on appeal. National Treasury Employees Union v. Internal Revenue Serv., 765 F.2d 1174, 1176 n. 1 (D.C.Cir.1985). In the habeas context, where we proceed on collateral review, the notion of waiver applies, though it typically takes the form of the procedural default rule. Under that rule, when “the claim has not been presented to the state court ... it is now barred” unless the petitioner can show cause for the default and actual prejudice. Bassette v. Thompson, 915 F.2d 932, 937 (4th Cir.1990). We follow that rule vigorously, Justice O’Connor explained in Teague, and “have declined to make the application of the [rule] dependent on the magnitude of the constitutional claim at issue, or on the State’s interest in the enforcement of its procedural rule.” 489 U.S. at 308, 109 S.Ct. at 1074 (citations omitted).
The reason for our close adherence to the rule is that “the underlying considerations of finality,” which Justice O’Connor saw underpinning the finality of civil judgments, “find significant and compelling parallels in the criminal context.” Id. at 309, 109 S.Ct. at 1074. We agree. See Bassette, 915 F.2d at 935-37. However, finality, and its companion, waiver, must *459run along a two-way street. Finality certainly means that a petitioner cannot raise new claims on appeal not yet raised. It also must mean that the State cannot raise new defenses on appeal not raised below.
In Maynard v. Dixon, 943 F.2d 407, 418 (4th Cir.1991), this court reached the merits of the petitioner’s Mills/McKoy claim because it assumed without deciding that the State had waived the Teague defense. We agree with the Maynard court and the Seventh Circuit that a state’s failure to raise the issue of retroactivity below constitutes waiver of that defense.
In this case, Williams raised the Mills issue before the district court, and the court rejected his claims on their merits. The State did not raise the retroactivity question in this case at the district court level, although retroactivity claims have been made for the last 25 years. See Hanrahan, 896 F.2d at 245. Even after Teag-ue was decided, the State did not raise the retroactivity issue in its first arguments before this court. It was not until the decision was handed down in McKoy that the State decided to raise the retroactivity issue. We believe that was too late. On the facts before us, the State “missed the boat,” Hanrahan, 896 F.2d at 245, and waived any Teague defense to the application of McKoy and Mills in this case.
V
To summarize, we do not disturb Williams’ conviction as the trial court made no constitutional errors concerning the guilt phase of the trial. However, we vacate Williams’ sentence of death and remand the ease for resentencing because the jury instructions were unconstitutional under the rules set out in Mills and McKoy. Williams may benefit from the Mills and McKoy rules because they are bedrock procedural rules falling within the second exception to the Teague rule. As an independent and alternative ground, we vacate Williams’ sentence and remand for resentencing because the State waived any Teague defenses to the retroactive application of these rules by its failure to raise the issue at the district court level or at the first hearing before this court.
In light of our holding on the McKoy issue, at this time we need not address Williams’ assignments of error concerning post-trial proceedings.
AFFIRMED IN PART; VACATED AND REMANDED IN PART.
. These included a Motion to Provide Funds for Experts and Investigative Assistance, a Motion to Produce Exculpatory Information, a Motion for Finding of Indigency, and a Motion for Independent Psychiatric Testing.
. The Supreme Court has defined final to mean where the judgment of conviction has been rendered, the availability of appeal has been exhausted, and the time for petition for certiorari has elapsed. Allen v. Hardy, 478 U.S. 255, 258 n. 1, 106 S.Ct. 2878, 2880 n. 1, 92 L.Ed.2d 199 (1986) (quoting Linkletter v. Walker, 381 U.S. 618, 622 n. 5, 85 S.Ct. 1731, 1734 n. 5, 14 L.Ed.2d 601 (1965)).
. We note that a previous panel of this court made a statement on this issue in McDougall v. Dixon, 921 F.2d 518 (4th Cir.1990). There, we held that McKoy did not apply to the defendant’s case, id. at 539; however, we went on to state the following:
McKoy is an extension of Mills v. Maryland, which was decided eight years after McDougall’s conviction. The McDougall facts are not the same as' McKoy, but even if they were, the McKoy and Mills cases represent new law and would not be applied retroactively on collateral review. Teague v. Lane, 489 U.S. 288, 109 S.Ct. 1060, 103 L.Ed.2d 334 (1989).
Id.
. The court asked: "Do you unanimously find that one or more of the following mitigating circumstances existed at the time of the murder?”
. In that order, the district court addressed the merits of the Mills claim raised by Dixon and held that the jury instructions did not violate the Mills rule. (JA Vol I, Tab E, at 30-36.)
. In its supplemental brief, the State explained: "The State’s assertion of non-retroactivity in this case, while admittedly not made in the District Court, is based upon and dictated by the 'novel threshold test for federal review of state criminal convictions’ announced in Teague.” (Supplemental Brief for Appellee at 36.)