In 2011, Appellant Michael Holmes's 2006 sentence for drug and firearm possession was vacated following investigations into former St. Louis Metropolitan Police Officers Shell Sharp and Bobby Garrett, who were found to have engaged in illegal activity while employed at the St. Louis Metropolitan Police Department. After his sentence was vacated, Holmes sought a certificate of innocence, which the district court1 denied. He subsequently filed a Fed. R. Civ. P. 60(b) motion for relief from *788the district court's judgment, which the court also denied. Holmes appeals, arguing that the district court abused its discretion when it found he was not actually innocent of the crimes for which he was charged and when it denied his Rule 60(b) motion. We disagree and affirm.
I. Background
In December 2003, Sharp, Garrett, and Officer Alan Ray arrested Holmes in a residence located at 5894 Cates Avenue (the "Cates Residence ") and searched the home. During the search, officers found mail addressed to Holmes at the Cates Residence in addition to cash, drugs, drug paraphernalia, and a gun. In 2006, a jury found Holmes guilty of possessing more than 50 grams of cocaine base with intent to distribute in violation of 21 U.S.C. § 841(a)(1) and possession of firearms in furtherance of a drug trafficking crime in violation of 18 U.S.C. § 924(c). Sharp was the only witness who testified at Holmes's trial about the events leading up to Holmes's arrest. Ray was unavailable to testify because he was deployed with the military overseas.
In 2009, the St. Louis Metropolitan Police Department began investigating allegations that Sharp had given perjured testimony and falsified affidavits in many of his cases. As a result, the St. Louis Circuit Attorney's office dropped the charges in criminal cases in which Sharp had been involved. Additionally, the same year, Garrett pled guilty to several federal crimes stemming from illegal activities he engaged in as a police officer. Following these investigations, the government no longer vouched for the testimony of the two officers.
In 2011, Holmes filed a motion to vacate, correct, or set aside his 2006 sentence pursuant to 28 U.S.C. § 2255. Based on Sharp and Garrett's history of perjury and falsifying evidence, the district court granted Holmes's motion to vacate, concluding the remaining evidence absent Sharp's testimony was insufficient to prove guilt beyond a reasonable doubt. In 2012, Holmes moved for a certificate of innocence pursuant to 28 U.S.C. §§ 1495, 2513.
In response to Holmes's motion for a certificate of innocence, the Government submitted a declaration that Ray gave in 2011 recalling the events on the night of Holmes's arrest. Ray stated that he and Sharp: surveilled Holmes at the Cates Residence and watched him conduct what they believed to be drug transactions; saw Holmes drop a paper bag containing crack and run up the stairs to the third floor of the Cates Residence; and discovered mail addressed to Holmes, cash, drugs, drug paraphernalia, and a gun in the upstairs bedroom. He also stated that Holmes admitted to living at the Cates Residence and that the bedroom where they arrested him was his.
Holmes testified that he was innocent and offered documentary evidence that he resided at a different location and photo evidence of the staircases in the Cates Residence in an attempt to prove that Ray's declaration was false. The district court credited Ray's declaration and accompanying evidence and denied Holmes's motion for a certificate of innocence.
While the certificate of innocence proceedings were pending in the district court, Holmes, in a separate case, filed 42 U.S.C. § 1983 claims against Sharp and Garrett, but not Ray. Following the district court's denial of a certificate of innocence, Holmes received a favorable verdict against Sharp and Garrett on his § 1983 claims. Based on this verdict, Holmes filed a Rule 60(b) motion for relief from the court's judgment on the certificate of innocence, arguing that the verdict was new evidence establishing his actual innocence.
*789The district court denied the motion, finding that the jury verdict was not new evidence. Holmes appeals.
II. Discussion
Holmes identifies two issues on appeal. First, he challenges the district court's ruling on his certificate of innocence motion, asserting that the district court erred when it found he did not prove actual innocence. Second, he claims that the district court erred when it denied his Rule 60(b) motion for relief from its judgment on his certificate of innocence request because the favorable jury verdict in his § 1983 case was new evidence of actual innocence. We address each claim in turn.
A. Certificate of Innocence
"[A] certificate of innocence is civil in nature ... [and] serves ... to permit its bearer to sue the government for damages" related to a wrongful conviction. Betts v. United States, 10 F.3d 1278, 1283 (7th Cir. 1993). For Holmes to obtain a certificate of innocence, he must demonstrate that his conviction:
(1) 'has been reversed or set aside on the ground that [he] is not guilty of the offense of which [he] was convicted ... and (2) ... [his] acts, deeds, or omissions in connection with such charge constituted no offense against the United States, or any State ... and [he] did not by misconduct or neglect cause or bring about [his] own prosecution.'
United States v. Racing Servs., Inc., 580 F.3d 710, 712 (8th Cir. 2009) (quoting 28 U.S.C. § 2513(a) ).
"A reversal of the criminal conviction based on insufficiency of the prosecution's evidence does not entitle the defendant to a certificate of innocence." Id. Defendants must instead, by a preponderance of the evidence, United States v. Grubbs, 773 F.3d 726, 733 (6th Cir. 2014), "persuade the district judge who presided over their criminal prosecution that they were truly innocent of all crimes to qualify for civil damage relief," Racing Servs., 580 F.3d at 713. Though the evidence may be insufficient to prove a defendant guilty of an offense, it can still "create so strong a belief in [the district court's] mind that petitioner was guilty of [that offense], that [the district court] would not feel justified in certifying that he was not guilty of this crime." Id. (second alteration in original) (internal quotation marks omitted).
Denying "a certificate of innocence is committed to the sound discretion of the district court." Racing Servs., 580 F.3d at 713. We will only reverse "in a case in which the refusal to certify innocence was completely capricious and without rational basis." Id. (internal quotation marks omitted); see also In re Guidant Corp. Implantable Defibrillators Prods. Liab. Litig., 496 F.3d 863, 866 (8th Cir. 2007) ("We will find an abuse of discretion only when the district court's judgment was based on clearly erroneous fact-findings or erroneous conclusions of law." (internal quotation marks omitted) ).
We give even greater deference to the district court's factual findings when they "are based on determinations regarding the credibility of witnesses." Anderson v. City of Bessemer City, 470 U.S. 564, 575, 105 S.Ct. 1504, 84 L.Ed.2d 518 (1985). The court's findings are not insulated from review, but if they are "based on [the court's] decision to credit the testimony of one of two or more witnesses, each of whom has told a coherent and facially plausible story that is not contradicted by extrinsic evidence, [those] finding[s], if not internally inconsistent, can virtually never be clear error." Id. Furthermore, "[f]actual findings cannot be clearly erroneous when the evidence permits two possible views."
*790In re BLT II, Ltd., 870 F.2d 456, 457 (8th Cir. 1989).
It is undisputed that Holmes "did not by misconduct or neglect cause or bring about [his] own prosecution." Racing Servs., 580 F.3d at 712 (quoting 28 U.S.C. § 2513(a) ). Thus, Holmes's appeal hinges on whether he has demonstrated actual innocence. Id. Here, the district court heard conflicting evidence regarding Holmes's actual innocence. First, Holmes testified that he was innocent. Second, he presented documentary evidence that he asserts shows he did not reside at the Cates Residence. Third, he put forth photographic evidence of the front staircase at the Cates Residence, which he claims undermines Ray's testimony because the photos prove he could not have run up the front stairs-the only stairs visible from the front of the residence-to the third floor since the front stairs only reach the second floor.
The Government, on the other hand, presented a declaration by Ray, whose credibility has not been impugned, that he: personally witnessed Holmes conducting drug transactions; saw Holmes drop a brown bag that contained crack and run up the stairs to the third floor of the residence; arrested Holmes in the Cates Residence; heard Holmes admit he lived in the Cates Residence; and found cash, drugs, drug paraphernalia, a weapon, and mail addressed to Holmes in Holmes's bedroom in the Cates Residence. Ray never specified whether he saw Holmes run up the front stairs or the rear stairs to the third floor.
The evidence presented permitted two possible views: (1) a finding that Holmes's testimony was reliable, the documents and photos he presented bolstered his testimony, and he was actually innocent of all crimes; or (2) a finding that Ray's declaration was reliable, the evidence seized on the premises supported Ray's declaration, Holmes's additional evidence did not undermine Ray's declaration, and Holmes was not actually innocent. The court was free to credit either witness and to interpret the evidence either way. See Grubbs, 773 F.3d at 733-34 (finding that in the face of conflicting evidence, the district court was within its right to credit one witness's testimony over the other's in denying a certificate of innocence). The district court chose to credit Ray's testimony, finding that because Ray was present during the events that took place and has not been discredited, neither his declaration nor the mail, cash, drugs, drug paraphernalia, and gun that the officers seized were tainted by Sharp's discredited testimony. The court held that this evidence could establish Holmes's guilt, and thus he had not met his burden of proving actual innocence. Because the evidence permitted two possible views, the district court's decision to credit Ray and find that Holmes did not prove his actual innocence was not "completely capricious and without rational basis." Racing Servs., 580 F.3d at 713 (internal quotation marks omitted).
Holmes further argues that the district court erred because it did not conduct an evidentiary hearing on his certificate of innocence motion. The statute does not direct the courts "as to what procedure a court should follow in determining whether or not a petitioner is entitled to a certificate." Grubbs, 773 F.3d at 732 (internal quotation marks omitted). We agree with the Sixth Circuit's determination that "the trial court may rely primarily on the record of the trial of the petitioner and that other relevant facts could be presented orally or by affidavit." Id. (internal quotation marks omitted). Therefore, we find that the district court did not abuse its discretion when it chose to rely on the trial record and other relevant facts presented *791by affidavits rather than conducting an evidentiary hearing. See id.
B. Rule 60(b) Motion
Next, Holmes argues that the district court erred when it denied his motion for relief from judgment under two subsections of Rule 60(b). He claims the evidence he presented in his § 1983 trial and the jury verdict from that case constitute sufficient evidence to warrant relief from the district court's denial of his certificate of innocence.
Rule 60(b) provides in relevant part that:
On motion and just terms, the court may relieve a party or its legal representative from a final judgment, order, or proceeding for the following reasons:
...
(2) newly discovered evidence that, with reasonable diligence, could not have been discovered in time to move for a new trial under Rule 59(b);
...
(6) any other reason that justifies relief.
"The denial of a Rule 60(b) motion is reviewed for an abuse of discretion." In re Guidant Corp., 496 F.3d at 866. "We will find an abuse of discretion only when the district court's judgment was based on clearly erroneous fact-findings or erroneous conclusions of law." Id. (internal quotation marks omitted). We do not view Rule 60(b) motions favorably. Harley v. Zoesch, 413 F.3d 866, 871 (8th Cir. 2005). "Reversal of a district court's denial of a Rule 60(b) motion is rare because Rule 60(b) authorizes relief in only the most exceptional of cases." In re Guidant Corp., 496 F.3d at 866 (internal quotation marks omitted).
We first consider Holmes's motion as it relates to Rule 60(b)(2). To succeed under Rule 60(b)(2), Holmes must establish four elements: "(1) the evidence was discovered after trial; (2) due diligence was exercised to discover the evidence; (3) the evidence is material and not merely cumulative or impeaching; and (4) the evidence is such that a new trial would probably produce a different result." U.S. Xpress Enterprises, Inc. v. J.B. Hunt Transp., Inc., 320 F.3d 809, 815 (8th Cir. 2003) (internal quotation marks omitted).
Holmes argues that the jury verdict in the § 1983 trial undermines Ray's § 1983 trial testimony and demonstrates that Ray was not a credible witness. However, while the jury returned a verdict with interrogatories that required separate findings as to Garrett and Sharp, there is no reference to Ray on the verdict form whatsoever. As such, it is impossible to know whether the civil jury found for Holmes because it believed Ray was not credible or that its finding was based on other evidence, or the lack thereof, presented at trial. Additionally, Ray's trial testimony that he saw Holmes in the stairwell, that Holmes dropped a brown bag and ran up the stairs to the third floor, and that Ray chased Holmes up the stairs to the bedroom, does not conflict with or exclude the possibility that Sharp and Garrett violated Holmes's civil rights by fabricating evidence, conspiring against him, maliciously prosecuting him, or falsely imprisoning him. Thus, we disagree with Holmes that the jury verdict necessarily undermines Ray's credibility, creating an exceptional circumstance requiring a new certificate of innocence proceeding.
Holmes further claims that the jury verdict is new evidence that definitively establishes actual innocence entitling him to relief from the district court's judgment. The jury verdict itself is a new piece of evidence-the result of Holmes's § 1983 case against Sharp and Garrett. The verdict was delivered on March 4, 2016, four *792months after the district court's November 3, 2015 denial of Holmes's request for a certificate of innocence. Thus the evidence could not have been discovered before the certificate of innocence proceeding. The jury verdict is also material to the question of Holmes's actual innocence, as a finding that Sharp and Garrett fabricated evidence against Holmes is certainly an important consideration in determining whether Holmes is actually innocent of the charges levied against him. See United States v. Hernandez, 299 F.3d 984, 990 (8th Cir. 2002) ("Evidence is material if there is a reasonable probability that the outcome of the proceeding would have been different if the evidence had been disclosed.").
However, the jury verdict is not evidence that if presented in a new certificate of innocence proceeding "would probably produce a different result." U.S. Xpress, 320 F.3d at 815 (internal quotation marks omitted). First, the jury's finding that Sharp and Garrett fabricated evidence, conspired against, maliciously prosecuted, and falsely imprisoned Holmes is not a finding that Holmes is actually innocent. Rather, as the district court recognized, it is only a finding that Sharp and Garrett violated Holmes's rights. Second, the district court, just as the jury in Holmes's § 1983 case, was free to weigh the credibility of the witnesses and the other evidence before it. Anderson, 470 U.S. at 575, 105 S.Ct. 1504. That the jury in the § 1983 case found that Sharp and Garrett violated Holmes's civil rights does not necessitate that the district court find that Ray is not a credible witness and that Holmes did not actually commit any of the crimes for which he was charged. See Racing Servs., 580 F.3d at 713. Moreover, the district court expressly stated that it was aware of Sharp's and Garrett's fraudulent conduct, as it was the basis for the court's decision to vacate Holmes's sentence in the first place. Because the jury verdict is not a finding of actual innocence and the court had previously considered Sharp's and Garrett's fraudulent conduct and still held that Holmes had not shown actual innocence, it is unlikely that additional evidence of the same fraudulent conduct would prompt a different result in a new proceeding.
Next, we consider Holmes's argument based on Rule 60(b)(6). Under Rule 60(b)(6), relief is only available "where exceptional circumstances have denied the moving party a full and fair opportunity to litigate his claim and have prevented the moving party from receiving adequate redress." Harley, 413 F.3d at 871.
Holmes has had several opportunities to fully and fairly litigate his claims through his motion to vacate his conviction, his motion for a certificate of innocence, his § 1983 claim, and his Rule 60(b) motion for relief from judgment. Id. Granting a Rule 60(b) motion is extraordinary relief, id., and the jury's verdict in the § 1983 proceeding, because it is not a finding of actual innocence, does not constitute an exceptional circumstances under Rule 60(b)(6). Moreover, as we held above, the district court was free to credit either Holmes or Ray, and its decision to credit Ray was not capricious or unfair.
Therefore, we find the district court did not abuse its discretion in denying Holmes's Rule 60(b) motion.
III. Conclusion
For the foregoing reasons, we affirm the district court's denial of Holmes's request for a certificate of innocence and his subsequent Rule 60(b) motion for relief from judgment.