The State of Texas charged Christopher Joseph Salazar (“Salazar”) with capital murder. Salazar’s counsel filed a pretrial motion to suppress a confession he gave to law enforcement officials. A Texas court denied the motion. Salazar and Texas then struck a plea bargain in which Salazar pled guilty to aggravated robbery in return for a dismissal of all other charges. At the plea colloquy, the state court did not inform Salazar of his right under state law to appeal a pretrial ruling as of right or of his federal right to court-appointed counsel if he was unable to pay an appellate attorney. To the contrary, the state court told Salazar that if the plea was accepted, Salazar would be unable to appeal without the court’s permission. The state court accepted Salazar’s plea and sentenced him to a term of 60 years.
Eight years after his conviction, Salazar filed his second2 application for a state writ of habeas corpus alleging ineffective assistance of counsel. Specifically, Salazar alleged that his trial attorney, Mark Vela (“Vela”), rendered ineffective assistance by failing to properly inform him of his appellate rights. Salazar attached an affidavit in which he swore that, in response to his inquiry regarding the possibility of an appeal, Vela informed him that it would be ridiculous to appeal something to which Salazar had agreed. Salazar further swore that Vela never informed him of his statutory right to appeal pretrial rulings with appointed counsel and without leave of the court.
The state habeas court ordered Vela to produce an affidavit. Vela complied, and swore that because he had litigated the case eight years ago, he was unable to remember *791whether he had informed Salazar that Texas law allowed an appeal as of right from pretrial rulings with appointed counsel. Vela was able to remember, however, that “an appeal was the furthest thing from Mr. Salazar’s mind at the time, in that he was trying to avoid the death penalty, that’s the reason he accepted the plea bargain agreement in that he appeared to be perfectly satisfied with the results at that point.”
The state habeas judge, a different judge from the one accepting Salazar’s guilty plea, made findings of fact and conclusions of law without a hearing. The court found Vela’s affidavit credible and Salazar’s incredible. On the basis of this credibility determination, the court found that Salazar “did not wish to appeal his conviction in the primary case.” Finally, the court found that Salazar had failed to prove by a preponderance of the evidence that but for counsel’s allegedly deficient performance, Salazar would have demanded a full trial on the merits. The court then concluded that because Salazar had not intended to appeal his conviction, he had not proved that Vela rendered ineffective assistance or that he had been prejudiced.
Thereafter, Salazar sought relief in the Federal Court pursuant to 28 U.S.C. § 2254. His primary argument was ineffective assistance of counsel. The district court decided the case on summary judgment. That court interpreted the state court’s opinion as including an implicit finding that Salazar was informed of his right to appeal his conviction. The district court then applied a presumption of correctness to this implicit finding as well as the state court’s explicit finding that Salazar had no desire to appeal his conviction. On the strength of these two findings, as well as the state court’s conclusions of law, the district court denied Salazar relief on his sixth amendment claim.
On appeal, Salazar challenges the district court’s decision to accord the state court’s factual findings a presumption of correctness, arguing that, in this case, a paper hearing was insufficient to form the basis for the denial of habeas relief. We agree.
Standard of Review
Pursuant to 28 U.S.C. § 2254(d), “a federal court is to accord a presumption of correctness to findings of state court proceedings unless particular statutory exceptions to a § 2254(d) are implicated.” Williams v. Collins, 16 F.3d 626, 631 (5th Cir.), cert. denied, - U.S. -, 115 S.Ct. 42, 129 L.Ed.2d 937 (1994). The panel reviews the district court findings “for clear error, but decides any issues of law de novo.” DeVille v. Whitley, 21 F.3d 654, 656 (5th Cir.), cert. denied, - U.S. -, 115 S.Ct. 436, 130 L.Ed.2d 348 (1994). This Court reviews mixed questions of fact and law such as ineffective-assistance-of-counsel claims de novo. United States v. Faubion, 19 F.3d 226, 228 (5th Cir.1994).
Analysis
Salazar contends that his counsel was ineffective in failing to inform him of his appellate rights. Ordinarily, to prevail on a claim of ineffective assistance of counsel, a petitioner must show that his counsel’s performance was both deficient and prejudicial to the petitioner. Strickland v. Washington, 466 U.S. 668, 689-94, 104 S.Ct. 2052, 2065-68, 80 L.Ed.2d 674 (1984). Thus, “[a]n attorney’s advice not [to] appeal is subject to the same tests as other claims of ineffective assistance of counsel.” Faubion, 19 F.3d at 231. However, when the eomplained-of actions result in the actual or constructive denial of the assistance of counsel altogether, a petitioner need not prove prejudice under Strickland. Childs v. Collins, 995 F.2d 67, 68 (5th Cir.) (citing Penson v. Ohio, 488 U.S. 75, 88, 109 S.Ct. 346, 354, 102 L.Ed.2d 300 (1988), cert. denied, 510 U.S. 1016, 114 S.Ct. 613, 126 L.Ed.2d 577 (1993)). “If a petitioner can prove that the ineffective assistance of counsel denied him the right to appeal, then he need not further establish — as a prerequisite to habeas relief — that he had some chance of success on appeal.” United States v. Gipson, 985 F.2d 212, 215 (5th Cir.1993).
Factual findings based solely on a paper record are not automatically entitled to a presumption of correctness. Amos v. Scott, 61 F.3d 333, 347 (5th Cir.), cert. denied, - U.S. -, 116 S.Ct. 557, 133 *792L.Ed.2d 458 (1995). Generally, “it is necessary to examine in each case whether a paper hearing is appropriate to the resolution of the factual disputes underlying the petitioner’s claim.” May v. Collins, 955 F.2d 299, 312 (5th Cir.), cert. denied, 504 U.S. 901, 112 S.Ct. 1925, 118 L.Ed.2d 533 (1992). In Nethery v. Collins, 993 F.2d 1154, 1157 n. 8 (5th Cir.1993), cert. denied, - U.S. -, 114 S.Ct. 1416, 128 L.Ed.2d 87 (1994), this court refused to afford a presumption of correctness to a state court finding, despite the submission of conflicting affidavits on the issue, when the habeas proceeding was not considered by the same judge who had presided over the petitioner’s trial. See also Perillo v. Johnson, 79 F.3d 441 (5th Cir.1996) (not according presumption of correctness when state habeas judge was not the judge at the state trial).
It is unclear whether the paper hearing in the instant case was adequate to resolve Salazar’s ineffective assistance of counsel claim. The state judge who presided over Salazar’s no contest plea did not conduct the habeas proceeding. Arguably, Salazar and Vela presented competing versions as to whether Salazar wished to appeal his conviction. Furthermore, Salazar admits that he knew of the theoretical availability of an appeal but contends that his counsel failed to properly inform him of his appellate rights. This assertion was never disputed by Vela, instead Vela stated that he simply could not remember whether he had informed Salazar of his appeal rights. Nevertheless, the district court states that the state court “implicitly found” that Salazar was informed of his appellate rights.
The district court’s reliance on this implicit finding by the state court was unsupported by the record. Likewise, attaching a presumption of correctness to this supposed implicit finding was erroneous. Accordingly, REMAND is required to determine whether Salazar was informed of his right to appeal his conviction and thus, whether Vela rendered ineffective assistance of counsel.