In United States v. Gallego, 247 F.3d 1191 (11th Cir.2001), we affirmed petitioner Abel Rizo’s convictions. In January 2003, petitioner moved the district court pursuant to 28 U.S.C. § 2255 to vacate his convictions on the ground that his trial attorney rendered ineffective assistance of counsel at trial. The court referred the motion to a magistrate judge who issued a Report and Recommendation (“R & R”) recommending that the district court deny the motion without holding an evidentiary hearing. The magistrate judge made that recommendation after concluding that the record of the trial proceedings conclusively established that the motion was without merit and that the affidavits petitioner proffered in support of his motion contained nothing to warrant an evidentiary hearing. The district court overruled petitioner’s objections to the R & R and denied the motion.
Petitioner now appeals the ruling. The issue before us, which the district court certified in its certificate of appealability, is whether “the district court err[ed] in denying [Rizo’s] claim that his trial counsel was ineffective for failing to interview or call alibi witnesses without holding an evi-dentiary hearing?”
We review the district court’s denial of an evidentiary hearing for abuse of discretion. Aron v. United States, 291 F.3d 708, 714 n. 5 (11th Cir.2002). An evidentiary hearing must be held on a motion to vacate “[u]nless the motion and the files and records of the case conclusively show that the prisoner is entitled to no relief.” 28 U.S.C. § 2255(b). “[T]o be entitled to an evidentiary hearing, a [movant] need only allege-not prove-reasonably specific, non-conclusory facts that, if true, would entitle him to relief. If the allegations are not affirmatively contradicted by the record and the claims are not patently frivolous, the district court is required to hold an evidentiary hearing.” Aron, 291 F.3d at 715 n. 6 (emphasis in original). “[C]on-tested fact[ual] issues in § 2255 cases must be decided on the basis of an evidentiary hearing, not affidavits.” Montgomery v. United States, 469 F.2d 148, 150 (5th Cir.1972).1
To prevail on a claim of ineffective assistance of counsel, a prisoner must show both that (1) his counsel’s performance was deficient, and (2) the deficient performance prejudiced his defense. Strickland v. Washington, 466 U.S. 668, 687, 104 S.Ct. 2052, 2064, 80 L.Ed.2d 674 (1984). To establish deficient performance, the prisoner must prove, by a preponderance of the evidence, that counsel’s performance was unreasonable. Chandler v. United States, 218 F.3d 1305, 1313 (11th Cir.2000) (en banc). “[C]omplaints of uncalled wit*266nesses are not favored, because the presentation of testimonial evidence is a matter of trial strategy and because allegations of what a witness would have testified are largely speculative.” Buckelew v. United States, 575 F.2d 515, 521 (5th Cir.1978). “The mere fact that other witnesses might have been available ... is not a sufficient ground to prove ineffectiveness of counsel.” Waters v. Thomas, 46 F.3d 1506, 1514 (11th Cir.1995) (en banc). However, when counsel fails to investigate his client’s “only ... possible defense [ (that defendant was in another city when the crime was committed) ], although requested to do so by him; and fails to subpoena witnesses in support of the defense, it can hardly be said that the defendant” received effective assistance of counsel. Gomez v. Beto, 462 F.2d 596, 597 (5th Cir.1972).
To prove prejudice, the prisoner “must show that there is a reasonable probability that, but for counsel’s unprofessional errors, the result of the proceeding would have been different.” Strickland, 466 U.S. at 694, 104 S.Ct. at 2068. A reasonable probability is one sufficient to undermine confidence in the outcome. Id. The court must consider the totality of the evidence before the judge or jury in making the prejudice determination. Id. at 695, 104 S.Ct. at 2069. A verdict or conclusion only weakly supported by the record is more likely to have been affected by errors than one with overwhelming record support. Id. at 696, 104 S.Ct. at 2069.
Petitioner contends that his trial counsel was ineffective for failing to interview or call alibi witnesses who would have testified that he was not present at the scenes of the crimes charged, thereby affecting the trial’s outcome. After examining the affidavits attached to petitioner’s motion and the trial transcript, we cannot agree with the district court that the affidavits and transcript, considered as a whole, conclusively establish that counsel’s failure to pursue the potential alibi witnesses did not prejudice petitioner’s defense. We therefore vacate the district court’s judgment and remand the case with the instruction that the court hold an evidentiary hearing on petitioner’s ineffective assistance claim.
VACATED and REMANDED, with instructions.