Respondents-Appellants-Cross-Appel-lees Michael B. Cooksey, Warden U.S.P. Marion, and the Attorney General of the State of New York (collectively, “respondents”) ' appeal from a judgment of the United States District Court for the Southern District of New York (Brieant, J.) granting Petitioner-Appellee-Cross-Ap-pellant Frank Sacco’s (“Sacco”) petition for a writ of habeas corpus. Sacco also cross-appeals from the district court’s decision on the claims in support of his petition as to which he was unsuccessful. We hold that the district court erred in granting the writ and reverse the judgment below.
I.
Following a jury trial in the County Court of Orange County, New York in 1991, petitioner Sacco was convicted for the second degree murder of Robert Melo-ni (“Meloni”). Meloni operated a landfill owned by Sacco. The key prosecution witness, Frank Armento, was also involved in Sacco’s landfill business. Armento testified under a grant from the prosecution of use and transactional immunity. According to Armento’s trial testimony, he and Meloni met Sacco, between 7:30 and 7:45 p.m. on April 7, 1988, at a landfill in Montgomery, New York. Ten or fifteen minutes after Armento and Meloni arrived, Armen-to walked away from the group. He heard a “popping sound” and when he turned around, he saw Meloni lying on the ground and Sacco, who had a pistol in his hand, standing over the dead man. On direct examination, Armento specifically denied ever having confessed that he, rather than Sacco, committed the murder. The theory of the defense, however, was that Armento was the real killer and that he was framing Sacco.
The jury returned a verdict of guilty. Sacco pursued an unsuccessful direct appeal and, approximately three and one-half months after Judge Levine of the New York Court of Appeals denied leave to appeal, see People v. Sacco, 84 N.Y.2d 832, 617 N.Y.S.2d 152, 641 N.E.2d 173 (1994), Sacco, in December 1994, filed a pro se habeas petition, pursuant to 28 U.S.C. § 2254, challenging his future state custody.1 On October 4, 1995, the Southern District of New York dismissed the petition as mixed because state remedies had not been exhausted as to some of the grounds raised. Petitioner thereafter sought collateral relief in state court, pursuant to N.Y.Crim. Proc. Law § 440.10, on *273the basis, inter aha, that his trial counsel had been ineffective (a) for failing to put on three witnesses who would have testified that Armento had confessed the murder to them (“Additional Witnesses Claim”) and (b) for failing to utilize a transcript of a telephone conversation between Armento and Sacco in which Ar-mento admitted to placing two phone calls from his home at 7:11 p.m. and 7:23 p.m. on April 7, 1988 (“Telephone Conversation Claim”).2 Had Armento been at his home at this time, he could not have been at the Montgomery landfill between 7:30 and 7:45, -which, according to Armento’s trial testimony, was approximately the time that he witnessed Sacco murder Meloni. This is so because the landfill was an hour’s drive away from Armento’s home. The state courts declined to grant relief and, on February 5, 1997, Sacco filed this petition for federal habeas relief.
The district court referred the petition to a magistrate, who appointed counsel and authorized limited discovery. The magistrate recommended denial of the petition. The district court accepted the magistrate’s report in part and rejected it in part. Thus, the court granted the petition, ruling that petitioner had received ineffective assistance of counsel on the basis of the Additional Witnesses Claim and the Telephone Conversation Claim. But the district court denied petitioner’s remaining claims, while granting a certificate of ap-pealability as to them. Respondents sought relief from the judgment granting the writ and the district court denied their motion.
Respondents now appeal from the grant of the petition and the denial of their motion for relief from the judgment. Counsel for petitioner has submitted a brief defending the decision below. Petitioner has also cross-appealed, pro se, from the decision below to the extent that it declined to grant the writ (or at least to hold an evidentiary hearing) on his remaining claims.
II.
We review de novo the decision of the district court to grant the writ. See Smalls v. Batista, 191 F.3d 272, 277 (2d Cir.1999). Even though Sacco’s prior petition was filed before the effective date of the Anti-Terrorism and Effective Death Penalty Act (“AEDPA”), the AEDPA applies to this case since the instant petition was filed after the statute took effect. See Mancuso v. Herbert, 166 F.3d 97, 101 (2d Cir.), cert, denied, 527 U.S. 1026, 119 S.Ct. 2376, 144 L.Ed.2d 779 (1999). But this petition does not constitute a “second or successive” filing within the meaning of the AEDPA because Sacco’s prior petition was dismissed for failure to exhaust all of the claims presented and not on the merits. See Slack v. McDaniel, — U.S.-, -, 120 S.Ct. 1595,1605,146 L.Ed.2d 542 (2000).
Under the AEDPA, “the writ may issue only if ... the state-court adjudication resulted in a decision that (1) ‘was contrary to ... clearly established Federal law, as determined by the Supreme Court of the United States,’ or (2) ‘involved an unreasonable application of ... clearly established Federal law, as determined by the Supreme Court of the United States.’” Williams v. Taylor, — U.S. -, -, 120 S.Ct. 1495, 1523, 146 L.Ed.2d 389 (2000) (quoting 28 U.S.C. § 2254(d)(1)). Applying this standard, the decision below cannot stand.
Petitioner’s counseled claims are that, for various reasons, he received ineffective assistance of counsel. In this respect, there is no doubt that Sacco “seeks to apply a rule of law that was clearly established at the time his state-court conviction became final” “because the merits of his claim are squarely governed by [the Su*274preme Court’s] holding in Strickland v. Washington, 466 U.S. 668, 104 S.Ct. 2052, 80 L.Ed.2d 674 (1984).” Id. at 1511.
The question before us therefore is whether the state court adjudication denying Sacco’s motions for collateral relief was “contrary to” or “involved an unreasonable application of’ Supreme Court precedent. Id. at 1523 (quoting 28 U.S.C. § 2254(d)(1)). In order to establish a violation of Strickland, petitioner must show that his “counsel’s performance was deficient,” and that “the deficient performance prejudiced the defense.” Strickland, 466 U.S. at 687, 104 S.Ct. 2052. Representation is ineffective if “counsel’s representation fell below an objective standard of reasonableness.” Id. at 688, 104 S.Ct. 2052. In denying Sacco’s motion for collateral relief, the state court held that an attorney’s performance would be deemed effective as long as it was “reasonable.” This is exactly the standard set forth in Strickland. See id. at 688, 104 S.Ct. 2052. And under this standard, the state court ruled that the trial counsel’s decisions not to call the additional witnesses or to use the telephone conversation did not constitute ineffectiveness. We cannot say that this ruling was contrary to or involved an unreasonable application of federal law because, in fact, both of the decisions made by the trial counsel were objectively reasonable.
Although the testimony of the additional witnesses would have been admissible for the purpose of impeaching Armento’s credibility, see People v. Wise, 46 N.Y.2d 321, 328, 413 N.Y.S.2d 334, 385 N.E.2d 1262 (1978), it is clear from the record that, quite apart from these uncalled witnesses, trial counsel had already “aggressively sought to destroy the credibility of the People’s witnesses,” had called one witness who testified to Armento’s alleged confession, and specifically had spent two days cross-examining Armento. People v. Sacco, Indict. No. 0545-89, Index No. 1479/90, reprinted at Respondents’ Appendix 72-81. In addition, the uncalled witnesses were, themselves, highly impeachable. They had either drug habits or criminal histories, and all also had strong motives to lie for Sacco. For trial counsel to decide not to put on these witnesses, when Armento’s impeachment both on similar and on other grounds had already been attempted by counsel and when those very witnesses were themselves impeachable, and could even be described as willing to perjure themselves, was reasonable.
Second, the telephone conversation as a whole was damaging to the defense or, at the very least, could reasonably have been construed as such.3 The conversation does include Armento’s statement that he was at home at about 7:30 on April 7, 1988. But it also contains Sacco’s statement that Armento had nothing to do with Meloni’s disappearance. And more significantly, the conversation as a whole could be interpreted as an obvious effort on Sacco’s part to construct an alibi for the evening of April 7, 1988. See, e.g., People v. Reynolds, 704 N.Y.S.2d 398, 399 (4th Dep’t 2000) (holding that, under New York law, a jury under analogous circumstances could infer that the defendant’s behavior evinced a “consciousness of guilt”). At the time of the conversation, Meloni’s body had not yet been uncovered and Armento *275had not yet begun cooperating with authorities. Accordingly, the prosecution could have argued to the jury that the telephone conversation permitted a strong inference of Sacco’s consciousness of guilt — for why else would he have tried to construct an alibi for a date that the authorities did not yet know coincided with a murder? While an innocent inference might conceivably be made from the telephone conversation, so too might a damaging one. And petitioner could not control what parts of the telephone conversation the jury would hear. Indeed, he does not dispute that had his counsel sought to introduce Armento’s statement regarding the timing of Armento’s whereabouts, the door would have been opened to admission of the entire telephone conversation. Because there was a significant potential downside to the introduction of this evidence, trial counsel’s decision to avoid its admission was objectively reasonable.4
We conclude that the district court erred in granting the writ on the basis of the Telephone Conversation Claim and the Additional Witness Claim. We have also reviewed all of Sacco’s remaining arguments in support of his petition and find them to be without merit; these arguments were properly rejected by the district court and do not warrant an evidentiary hearing. The judgment below is REVERSED.5
. Sacco is currently a federal prisoner but is being held on a detainer for a consecutive New York State prison sentence of 25 years to life, to be served upon his release from federal custody.
. Included in this claim is the contention that trial counsel should have used telephone records of Armento’s home phone number that prove that two phone calls were in fact made at that time.
. Respondents contend that the Telephone Conversation Claim was procedurally defaulted because it was not fully pursued in state court. They emphasize that this issue was raised in a § 440.10 motion, the denial of which Sacco never appealed. While that is true, it is also the case that (1) Sacco amended a petition for leave to appeal a different § 440.10 motion specifically to include the Telephone Conversation Claim, (2) the Appellate Division denied the petition after receiving and considering the amendment (i.e., after considering this claim), and (3) his unsuccessful motion for leave to appeal to the New York Court of Appeals also included this claim. Because this issue has been presented to all three levels of New York state courts and because a letter from the Clerk's Office of the Appellate Division indicated that this issue had been considered by the Appellate Division, we can fairly treat it as before us.
. Nor did counsel’s failure to use the underlying telephone records, which showed that two phone calls were placed from Armento’s home at 7:11 p.m. and 7:23 p.m. on April 7, 1988, violate petitioner's constitutional right to counsel. Even assuming the failure to introduce this evidence constituted deficient performance, petitioner suffered no prejudice. The telephone records by themselves showed only that someone, perhaps Armento's wife Jessica, made two phone calls from Armento's residence. They do not show that Armento, contraiy to his trial testimony, was at home at that time. Given the at best equivocal nature of this evidence, petitioner has not shown that the outcome of the trial would potentially have been different had the jury learned of the telephone records.
. Accordingly, we need not address respondents' argument that the district court should have granted their motion for relief from the judgment.