MAGILL, Circuit Judge.

Cornist Johnson appeals the magistrate judge’s 1 denial of his petition for habeas corpus relief. Johnson claims he received *797 ineffective assistance of counsel during his state court criminal trial because his attorney failed to: investigate the case adequately and prepare for trial; offer a theory of the ease or put forth evidence at trial; advise Johnson of the limitations on the state’s ability to use his prior convictions to impeach him; and seek the exclusion of inadmissible prior conviction evidence. The magistrate judge found that Johnson failed to meet his heavy burden of showing deficient performance and prejudice and held that even though the trial strategy of Johnson’s attorney failed, it was reasonable and therefore did not violate Johnson’s constitutional right to effective representation. Because we agree with the magistrate judge’s well-reasoned opinion, we affirm.

The police charged Johnson with burglary and theft of property of Archie Robinson’s home on January 30, 1985. Robinson reported that Johnson came to his house at about 10:00 a.m. on the day of the burglary and requested his empty drink bottles. 2 Robinson refused to give Johnson the bottles and Johnson left. Shortly thereafter, Robinson and his housemate, Mary Spencer, left for work. When they returned that night, they found that the back door had been kicked in and they had been robbed. Based on the eyewitness testimony of Hiram Graham, one of Robinson’s neighbors, the police arrested Johnson and charged him with burglary and theft of property. Graham testified that on the day of the crime he saw Johnson and another person coming out of Robinson’s house with a television at about 1:00 p.m. 3 On August 16, 1985, a jury convicted Johnson of both charges. The court sentenced him as a habitual offender under Arkansas law, 4 and sentenced him to twenty-six years. The core of the state’s case against Johnson consisted of the eyewitness testimony of Graham.

Graham initially denied to both the victim and the police that he had any helpful information. Twelve days after the crime, Graham came forward with his testimony. Johnson denied the charges and claimed that he was at a club at the time of the crime. Johnson gave his counsel names of witnesses who could corroborate his alibi. Johnson’s attorney, Bynum Gibson, claims he spoke to all of Johnson’s alibi witnesses at least twice; the first time was in Gibson’s office before the trial and the second was in the courtroom on the day of the trial. Gibson also claims that during these meetings, none of the witnesses were able to provide Johnson with an alibi.

The state called five witnesses in its case-in-chief. Gibson cross-examined each witness thoroughly. After the state concluded, Gibson moved for a directed verdict for acquittal, arguing that the state failed to offer proof on all of the elements of the charges. The court denied this motion. In chambers, Gibson told the judge that both he and Johnson were concerned with the damaging effect of Johnson’s prior convictions if Johnson testified. Gibson then told the judge that Johnson would not be testifying because both he and Johnson did not believe it was in Johnson’s best interest to do so. The judge asked Johnson whether he agreed with Gibson and Johnson said he did. Upon returning to the courtroom, Gibson informed the court that he would not be calling any witnesses or offering further proof. During his closing argument, Gibson told the jury that the state had not provided and could not provide sufficient proof to convict Johnson. He pointed out the weaknesses in the state’s case, paying special attention to the credibility of Graham’s testimony. The jury found Johnson guilty and the court sentenced him to eighteen years on the burglary charge and eight years on the theft of property charge to run consecutively.

Johnson appealed his conviction, retaining Gibson as his appellate counsel. After *798 Johnson exhausted his state remedies, he petitioned for habeas corpus relief in federal court. The United States magistrate judge presiding over his habeas petition held an evidentiary hearing to evaluate Johnson’s ineffective assistance of counsel claims. At the evidentiary hearing, Johnson stated that at trial and on appeal, he was dissatisfied with Gibson’s performance. He explained that he kept Gibson as his attorney for his appeal because he did not know he could have fired Gibson and retained another attorney. Johnson also claimed that he had wanted to testify at trial, but Gibson told him that if he testified, the state would be able to use his prior convictions 5 against him. Johnson pointed out that Rule 609 of the Arkansas Rules of Evidence would have prohibited the court from using his murder conviction because it was over ten years old. Johnson also argued that effective counsel would have also tried to use Rule 609 to suppress the arson conviction because it did not involve dishonesty or false statement.

The magistrate judge also heard testimony from Johnson’s alibi witnesses. One witness testified that he spoke to Gibson at both trials 6 for a brief period; another witness testified that she spoke with Gibson at the first trial; and the third witness testified that she spoke to Gibson at the second trial. All of the witnesses claimed that they had seen Johnson at the time of the crime and that they would have testified to that effect had they been called at trial. While none of the witnesses stated that they could remember seeing Johnson at the time of the crime, they all testified that they would have noticed his absence if he had left the club for longer than five or ten minutes.

Gibson's testimony at the evidentiary hearing conflicted with Johnson’s testimony and that of his alibi witnesses. Gibson provided two reasons, in addition to his prior convictions, for not calling Johnson to testify. Gibson claimed that Johnson would not have been a good witness because he was nervous and fidgety. Gibson also claimed that Johnson asserted that he did not want to testify. Gibson further testified that he spoke to ail of the alibi witnesses at least twice, once in his office before trial and once in court on the day of trial. Contrary to the witnesses’ testimony, Gibson testified that none of the witnesses were able to provide Johnson with an alibi. Furthermore, Gibson claims that in addition to their inability to place Johnson at the club at the time of the crime, the witnesses “weren’t the type that they would automatically be believed.” Evid. Hearing at 2-11. Since one of the witnesses was Johnson’s sister, it would not have been unreasonable for Gibson to believe that her familial bias would have further discredited her shaky alibi, ultimately hurting Johnson’s case. Gibson also testified that one of the witnesses came to the trial drunk and that calling her would have caused great damage to Johnson’s case. Gibson concluded that since none of the witnesses would provide Johnson with an alibi, calling them to the stand would have hurt Johnson more than it would have helped him.

Even though the magistrate judge found the testimony of the alibi witnesses fairly persuasive, he denied Johnson’s petition for habeas relief because he found that Johnson failed to meet his heavy burden of showing deficient performance and prejudice. The magistrate judge held that even though Gibson’s strategy failed, it was reasonable. Furthermore, the magistrate judge held that Gibson had the discretion to recommend whether Johnson should testify, independent of Rule 609 of the Arkansas Rules of Evidence. For these reasons and because Johnson assented to Gibson’s decision to not testify in the judge’s chambers, the magistrate judge concluded that this decision did not deprive Johnson of effective assistance of counsel.

*799 II.

Johnson argues on appeal that Gibson provided ineffective assistance because he failed to: investigate the case adequately and prepare for trial; offer a theory of the case or put forth evidence at trial; advise Johnson of the limitations on the state’s ability to use his prior convictions to impeach him; and seek the exclusion of inadmissible prior conviction evidence.

A.L. Lockhart, Director of the Arkansas Department of Correction, argues that Gibson’s representation of Johnson did not fall below an objective standard of reasonableness required by the Constitution. Additionally, Lockhart argues that even if Gibson’s performance was deficient, Johnson failed to show that but for Gibson’s alleged unprofessional errors, the result of Johnson’s trial would have been different.

In Strickland v. Washington, 466 U.S. 668, 104 S.Ct. 2052, 80 L.Ed.2d 674 (1984), the Supreme Court set forth a two-part test for ineffective assistance of counsel claims: first, a habeas petitioner must show that his or her counsel’s performance was deficient; and second, the habeas petitioner must show that the deficient performance prejudiced his or her defense. Id. at 687, 104 S.Ct. at 2064. The first part of the test requires a court to review counsel’s performance, considering all of the surrounding circumstances. Id. at 688, 104 S.Ct. at 2064. The Court also directed that judicial scrutiny of counsel’s performance be highly deferential because of the deceptive clarity of hindsight. Id. at 689, 104 S.Ct. at 2065. If a court determines that counsel’s performance fell below an objective threshold, then the court proceeds with the second part of the Strickland test. To satisfy this part, a habeas 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.

Johnson first claims that Gibson's representation was deficient because he did not fulfill his duty to investigate Johnson’s alibi. See Lawrence v. Armontrout, 900 F.2d 127, 129-30 (8th Cir.1990); Tosh v. Lockhart, 879 F.2d 412, 414 (8th Cir.1989); Thomas v. Lockhart, 738 F.2d 304, 308 (8th Cir.1984). In Lawrence, the attorney did not attempt to contact two witnesses who the defendant claimed could provide him an alibi. Lawrence, 900 F.2d at 129. We held that failure to make such a minimal effort fell “short of the diligence that a reasonably competent attorney would exercise under similar circumstances.” Id. at 129-30. In Johnson’s case, Gibson interviewed all of the witnesses at least once and subpoenaed them to assure that they would be present at trial if needed. Once an attorney interviews a witness, it becomes largely a matter of legal judgment as to whether the witness should be called to testify. Gibson testified at the evidentiary hearing that he based his decision not to call any of Johnson’s alibi witnesses upon his conclusions concerning their trustworthiness and credibility. While different lawyers could reasonably arrive at different conclusions based upon the same interview, the decision to call Johnson’s alibi witnesses was clearly a matter of trial strategy. This circuit has repeatedly warned against sec-ondguessing a lawyer’s trial strategy in evaluating claims of ineffective assistance of counsel. Laws v. Armontrout, 863 F.2d 1377, 1393-94 (8th Cir.1988); Hayes v. Lockhart, 852 F.2d 339, 352 (8th Cir.1988); Blackmon v. White, 825 F.2d 1263, 1265 (8th Cir.1987). Given Gibson’s decision to rely on the weakness of the state’s case and the conflicting testimony from the evi-dentiary hearing, we conclude that Gibson’s decision not to call the witnesses did not constitute ineffective assistance of counsel.

Johnson also claims that Gibson did not provide effective assistance of counsel because he failed to provide a theory of the case or put forth evidence at trial. The trial transcript refutes the first part of this claim. Gibson informed the jury of his theory of the case in both his opening statement and his closing argument. He told the jury that the government had not and could not meet its burden of proof of *800 guilt beyond a reasonable doubt. He pointed out the weaknesses in the state’s case and raised serious questions about the credibility of the state’s sole eyewitness. Gibson continued with this theme during his cross-examination of the state’s witnesses. While one may disagree with Gibson’s theory, he clearly had one.

The second part of this claim, that Gibson failed to put forth evidence at trial, is technically incorrect because cross-examination testimony is evidence. Nonetheless, it is true that Gibson did not introduce any physical, testimonial, or circumstantial evidence. However, the Constitution’s guarantee of effective representation does not require an attorney to submit any minimum amount or particular type of evidence. Since the government has the burden of proving guilt beyond a reasonable doubt, it may not be necessary for the defense to introduce evidence to meet the constitutional requirement of effective representation. Gibson thought that he was faced with such a case. Given the tenuous nature of the state’s case against Johnson and given that Gibson did interview Johnson’s alibi witnesses, Gibson’s trial strategy was not unreasonable and did not violate Johnson’s right to effective representation.

Johnson’s final ineffective assistance of counsel claim arises out of his decision not to testify. Johnson claims that Gibson failed to inform him of the state’s limited ability to use his previous convictions to impeach him. While this may well be true, Gibson testified at the evidentiary hearing that the possibility of the state using Johnson’s previous convictions to impeach him was not the only reason for his recommendation that Johnson not testify. Gibson testified that Johnson was very nervous and that Gibson believed that Johnson would not have been an asset to his defense. At the evidentiary hearing, Johnson claimed that he wanted to testify, but that Gibson advised him that it would be best for him not to take the stand because of his prior convictions. However, in the trial judge’s chambers, Johnson told the court that he agreed that it would be in his best interest not to testify for himself. Given that an attorney has the discretion to advise a client whether he should testify on his behalf, Gibson’s advice could at worst be called bad trial strategy, not constitutionally deficient legal performance. See Isom v. Lockhart, 847 F.2d 484, 486 (8th Cir.1988) (no ineffective assistance of counsel when defendant did not testify on his behalf because there was (1) conflicting testimony on whether defendant asked to testify on his behalf, and (2) a potential for impeachment even if the defendant did testify).

Because we hold that Gibson’s representation was not constitutionally deficient, we need not engage in Strickland’s prejudice analysis.

III.

For the foregoing reasons, we affirm the denial of Johnson’s petition for habeas corpus relief.

. The Honorable John F. Forster, Jr., United States Magistrate Judge for the Eastern District of Arkansas.

. Johnson claims he wanted to return the bottles to collect the deposit.

. The items stolen included a color television, a stereo, shirts, and jewelry.

.Ark.Stat.Ann. § 5-4-501 (1977).

. Johnson had two prior convictions. In 1969, Johnson pleaded guilty to second-degree murder. In 1978, Johnson pleaded nolo contendere to aggravated arson.

. Technically, Johnson had two trials. The first trial was held on July 23, 1985, in Arkansas City, Arkansas, and the second was held August 16, 1985, in McGehee, Arkansas. The first trial was declared a mistrial during jury voir dire.