Rudy Stanko, a pretrial detainee incarcerated at the Douglas County Correctional Center (DCCC) in Nebraska, brought this civil-rights suit under 42 U.S.C. § 1983 (2000) against certain DCCC officials (the defendants). Pursuant to the screening provision of the Prison Litigation Reform Act (PLRA), 28 U.S.C. § 1915A (2000),1 the District Court dismissed Stanko’s complaint as frivolous pri- or to service of process on the defendants. Stanko appeals the dismissal, and we reverse.
In determining whether the District Court properly dismissed Stanko’s complaint as frivolous under § 1915A, we review the record de novo and construe Stanko’s pro se complaint liberally. See Burke v. N.D. Dep’t. of Corr. & Rehab., 294 F.3d 1043, 1043-44 (8th Cir.2002). “A complaint is frivolous where it lacks an arguable basis either in law or in fact.” Williams v. Hopkins, 130 F.3d 333, 335 (8th Cir.) (quotation marks and citations omitted), cert. denied, 522 U.S. 1010, 118 S.Ct. 595, 139 L.Ed.2d 431 (1997).
In counts one and two of his complaint, Stanko asserts that the defendants violated his constitutional right to defend himself in his federal criminal trial by limiting his access to legal materials. Stanko alleges that the defendants denied him access to the law library and ignored his requests “to be on equal footing as his adversaries, i.e., to have immediate access to copy machines at the paper cost, his personal files with separators, word processor, lexis nexis or a similar internet program.” Complaint at 3-4. In dismissing Stanko’s complaint as frivolous, the District Court ruled that Stanko “misconstrues the scope of his constitutional right of access to the courts.” Mem. & Order of April 3, 2006, at 4. The District Court then cited cases discussing the access rights of convicted inmates who file lawsuits that attack their sentences or conditions of confinement. Id. at 4-5 (citing Cody v. Weber, 256 F.3d 764, 767-68 (8th Cir.2001) and Higgins v. Carpenter, 258 F.3d 797, 799-800 (8th Cir.2001), cert. denied, 535 U.S. 1040, 122 S.Ct. 1803, 152 L.Ed.2d 659 (2002)).
While Stanko is probably not entitled to all of the legal tools he seeks, we cannot say at this very early stage in the litigation that the whole of Stanko’s legal-access claim lacks an arguable basis in law or fact. “Pro se defendants [in criminal cases] have a right of access to adequate law libraries or adequate assistance from *625persons trained in the law.”2 United States v. Kind, 194 F.3d 900, 905 (8th Cir.1999) (quotation marks and citations omitted), cert. denied, 528 U.S. 1180, 120 S.Ct. 1217, 145 L.Ed.2d 1117 (2000). Given the dearth of a record in this case, we do not know how much access Stanko was given to DCCC’s law library or to assistance from a person trained in the law. Thus, we cannot say that Stanko’s legal-access claim is frivolous.
In count three of his complaint, Stanko asserts that the defendants violated his First Amendment right to the free exercise of religion by refusing to accommodate his religious diet of fruit and nuts. Stanko alleges that he is a member of the Church of the Creator. The District Court dismissed this count as frivolous on the grounds that Stanko “alleged no facts which suggest either that the Church of the Creator is a bona fide religion or, more important, that the consumption of nuts and fruit is a genuine dietary requirement of the religion.” Mem. & Order of April 3, 2006, at 3. The District Court appears to have placed too high a burden of pleading and proof on Stanko, a pro se litigant, particularly at this early stage in the litigation.
As noted above, a claim is only frivolous if it has no basis in fact or law. We cannot rule out the possibility that the facts and law support Stanko’s First Amendment claim. There is no evidence in the record indicating one way or the other whether the Church of the Creator is a “religion” for the purposes of First Amendment protection.3 See Love v. Reed, 216 F.3d 682, 687 (8th Cir.2000) (discussing “ ‘useful indicia’ of a religion for the purposes of First Amendment jurisprudence” (quoting Africa v. Pennsylvania, 662 F.2d 1025, 1032 (3rd Cir.1981), cert. denied, 456 U.S. 908, 102 S.Ct. 1756, 72 L.Ed.2d 165 (1982))). If the Church of the Creator is a religion protected by the First Amendment, then the District Court must consider whether Stanko’s belief in eating a diet of fruit and nuts is a “sincerely held” belief that is “based on a teaching” of the religion. Goff v. Graves, 362 F.3d 543, 547 (8th Cir.2004). Even then, Stanko’s claim will fail if DCCC’s refusal to provide Stanko a diet of fruit and nuts was rationally related to DCCC’s interest in maintaining prison security. Id. at 549. To be sure, Stanko’s religious-diet claim faces many obstacles. As more facts become known, the District Court will be in a position to determine whether this claim should be dismissed prior to trial. At this point, however, we believe that service of process is mandated.4
*626Finally, we must address the District Court’s finding that Stanko failed to exhaust administrative remedies before filing this § 1983 suit, as required by the PLRA. See 42 U.S.C. § 1997e(a) (2000). “Taking judicial notice of the court’s records in other cases,” the District Court concluded that Stanko “could not have completed the grievance procedures at DCCC, including the appeal which is an integral component of the exhaustion process, within the 24 days between his arrival at the DCCC and the date he filed his complaint.” Mem. & Order of April 3, 2006, at 6. We believe that the District Court acted prematurely and without adequate factual support when it reached this conclusion and relied on it as an alternative basis for dismissing Stanko’s complaint.
First, it is important to recognize that the PLRA exhaustion requirement is an affirmative defense under Rule 8(c) of the Federal Rules of Civil Procedure. Foulk v. Charrier, 262 F.3d 687, 697 (8th Cir.2001). The burden is on “the defendant asserting this affirmative defense”—not the plaintiff bringing a § 1983 claim—“to plead and prove it.” Id. Indeed, “the PLRA exhaustion requirement can be waived.” Id. Second, nothing in the current record indicates that Stanko failed to exhaust the administrative remedies available to him. The appendix to Stanko’s appellate brief includes letters from DCCC stating that Stanko’s grievance petitions on his legal-access and religious-diet claims were denied. The letters include the words “final order” and do not indicate that Stanko has the right to administratively appeal the decisions. While it may be true, as found by the District Court, that DCCC’s “two-step grievance process [required] an appeal to the Chief Deputy of Corrections,” Mem. & Order of April 3, 2006, at 6, there are simply too many unknown facts at this point in the litigation for a comprehensive analysis of Stanko’s compliance with the PLRA exhaustion requirement (should this affirmative defense be raised). The District Court erred in dismissing Stanko’s claims for failure to exhaust administrative remedies.
We stress that we express no view as to whether Stanko’s claims have merit. We simply conclude that Stanko’s complaint is not frivolous and should be served on the defendants. We therefore vacate the District Court’s dismissal of Stanko’s complaint and remand the case for further proceedings.