Jerry McCauley-Bey, serving a life sentence for second degree murder, a consecutive life sentence for first degree assault, and two concurrent thirty-year sentences for armed criminal action, petitioned in district court for a writ of habeas corpus. 28 U.S.C. § 2254. The district court conditionally granted the writ. The government appeals, and we reverse.
I.
On July 21, 1988, McCauley-Bey got into an argument with Garlón McCoy and several of McCoy’s friends. The argument began after an intoxicated McCoy urinated near McCauley-Bey and McCauley-Bey’s girlfriend, Sharon Mitchell. MeCauley-Bey’s friend, Ricky Hill, ran across the street and returned with two pistols. After the argument, McCoy and his friends got into a van. McCauley-Bey and Hill approached and McCauley-Bey began firing into the van. *1105After the first gun was emptied, McCauley-Bey took the second gun from Hill and continued shooting. McCoy was killed and his friend, Ronnie Patrick, was wounded in the knee.
After McCauley-Bey’s arrest but before trial, he received a letter dated June 8, 1989, from trial counsel, Herman Jimerson, stating that three witnesses, James Massey, Tyrone Mitchell, and Eva Washington, would not be called because of their prior criminal histories. McCauley-Bey responded with a letter dated June 12, 1989, expressing disappointment and stating that he still wanted the witnesses called. The witnesses did not testify. On June 29,1989, a jury found McCau-ley-Bey guilty.
Raising a claim of ineffective assistance of counsel based on his trial counsel’s failure to call the three witnesses, McCauley-Bey pursued state postconviction relief without success. McCauley-Bey was initially denied an evidentiary hearing on his ineffective assistance claim, but following appeal to the Missouri Court of Appeals, a hearing was held. State v. McCauley, 831 S.W.2d 741 (Mo.App.1992). In anticipation of the evidentiary hearing, McCauley-Bey requested access to his legal records and on July 16, 1990, was given at least part of his file. However, it is unclear precisely when McCauley-Bey received copies of the aforementioned correspondence with trial counsel. The evidentia-ry hearing was held on September 15, 1992. The state courts rejected McCauley-Bey’s claim of ineffective assistance of counsel and found that trial counsel failed to call the three witnesses because their names had not been given to him. McCauley v. State, 866 S.W.2d 892, 894-95 (Mo.App.1993).
On January 31, 1994, McCauley-Bey filed a federal petition for a writ of habeas corpus. McCauley-Bey reasserted his claim of ineffective assistance of counsel. On December 20, 1994, an evidentiary hearing was held to determine why the three witnesses had not been called by trial counsel. On October 25, 1995, the district court granted a conditional writ of habeas corpus. The government now appeals.
II.
On appeal, the government argues that the prejudice prong of the ineffective assistance of counsel test was not satisfied by counsel’s failure to call the three witnesses.1
The claim of ineffective assistance of counsel is a mixed question of law and fact. Laws v. Armontrout, 863 F.2d 1377, 1381 (8th Cir.1988) (en banc), cert. denied, 490 U.S. 1040, 109 S.Ct. 1944, 104 L.Ed.2d 415 (1989). Accordingly, the district court’s factual findings are subject to the clearly erroneous standard of review, while the district court’s legal conclusions are subject to de novo review. Id. at 1381-82.
To be successful in a claim of ineffective assistance of counsel a petitioner must demonstrate that counsel’s performance was deficient, and further, that the deficient performance prejudiced the defense. Strickland v. Washington, 466 U.S. 668, 687, 104 S.Ct. 2052, 2064, 80 L.Ed.2d 674 (1984). We need not decide if counsel was ineffective if sufficient prejudice is not shown. Id. at 697, 104 S.Ct. at 2069-70. To show prejudice, “[t]he defendant must show that there is a reasonable probability that, but for counsel’s unprofessional errors, the result of the proceeding would have been different.” Id. at 694, 104 S.Ct. at 2068. A reasonable probability is one sufficient to undermine confidence in the outcome. Id. “[I]n determining the existence vel non of prejudice, the court ‘must consider the totality of the evidence before the judge or jury.’ ” Kimmelman v. Morrison, 477 U.S. 365, 381, 106 S.Ct. 2574, 2586, 91 L.Ed.2d 305 (1986) (quoting Strickland, 466 U.S. at 695, 104 S.Ct. at 2068-69). Applying these standards here, the petitioner has not shown prejudice.
In this case, we are required to add the proffered testimony of McCauley-Bey’s *1106uncalled witnesses to the body of evidence that actually was presented at his trial. Using this hypothetical construct, we must gauge the likely outcome of a trial based on this total body of evidence. Prejudice exists if there is a reasonable probability that the outcome would be different than that at the actual trial. In conducting this analysis, we are mindful of: (1) the credibility of all witnesses, including the likely impeachment of the uncalled defense witnesses; (2) the interplay of the uncalled witnesses with the actual defense witnesses called; and (3) the strength of the evidence actually presented by the prosecution.
First, the credibility of the uncalled witnesses is a part of determining prejudice. Wilson v. Kemna, 12 F.3d 145, 147 (8th Cir.1994) (uncalled witness was married to defendant at the time and therefore was impeachable). McCauley-Bey’s three uncalled witnesses were all subject to impeachment. Neither James Massey, Tyrone Mitchell, nor Eva Washington came forward promptly. James Massey could have been impeached with a prior assault conviction. Tyrone Mitchell was the brother of McCau-ley-Bey’s girlfriend, Sharon Mitchell. Further, Tyrone Mitchell’s ability to observe could have been challenged. Initially, based on his testimony at the evidentiary hearing, Mitchell would have testified at trial that he saw the shooting, that he saw McCauley-Bey and Sharon Mitchell running from the shooting, and that he was ducking during the shooting. In addition, details of Tyrone Mitchell’s account are not consistent with the testimony of other witnesses who testified that the shooting took place at night with the shooter firing into the van while standing between a truck and the van. By contrast, Mitchell would have stated that the shooting took place at dusk and that he saw no truck. Mitchell was approximately three blocks away from the shooting; if the truck was there, it likely would have blocked Mitchell’s view.
Second, the testimony of the uncalled witnesses is not considered in a vacuum. Strickland specifically directs that the totality of the evidence be considered. 466 U.S. at 695, 104 S.Ct. at 2068-69. Thus, the interplay between the uncalled witnesses and the defense witnesses actually presented is at issue. McCauley-Bey presented himself, Ricky Hill, and Sharon Mitchell to establish that he was not the gunman. However, Ricky Hill was impeached by prior statements consistent with the government’s version of events. Previously, Hill had told police that both he and McCauley-Bey had fired the shots. He repeated that account when he entered his guilty plea. • Likewise, Sharon Mitchell was impeached using a prior statement to police that McCauley-Bey was the gunman. Thus, even if the uncalled witnesses were unimpeachable, which they clearly were not, their testimony would have been weakened when the same version of events was also told by two witnesses who earlier gave accounts consistent with the government’s witnesses.
Finally, there is no prejudice if, factoring in the uncalled witnesses, the government’s case remains overwhelming. Fast Horse v. Class, 87 F.3d 1026, 1029 (8th Cir.1996); United States v. Hubbard, 22 F.3d 1410, 1422 (7th Cir.1994), cert. denied, — U.S. -, 115 S.Ct. 762, 130 L.Ed.2d 660 (1995). The substantial evidence against McCauley-Bey convinces us that there is not a reasonable probability that the outcome of the trial would have been different if the 'uncalled witnesses had testified. The government presented four witnesses whose testimony contradicts the proffered testimony of the uncalled witnesses. John Robinson, Ricky Davis, Michael Norman, and Ronnie Patrick all testified that McCauley-Bey fired shots into the van. Robinson, Davis, and Norman also had previously identified McCauley-Bey as the gunman both in a photo array and a lineup.
III.
The district court erred in finding prejudice and did not give proper weight to the credibility of the uncalled witnesses, the interplay between the uncalled witnesses and the actual defense witnesses called, and the strength of the evidence presented by the *1107prosecution. For these reasons, the judgment of the district court is reversed.