OPINION
This case calls upon us to assess the propriety of the District Court’s grant of defendant’s motion to dismiss for failure to state a claim under Fed. R. Civ. P. 12(b)(6). Because we conclude that the District Court improperly considered material outside of the pleadings in ruling on the motion, we will vacate the order of dismissal and remand this case for further proceedings consistent with this opinion.
I. Background and Procedural History
As the parties are familiar with the facts and procedural posture of this case, we will provide only a brief synopsis of the events leading up to this appeal.
Plaintiff, Michael Stratechuk, is the father and legal guardian of two minor children who attend school in the South Orange-Maplewood School District. He filed suit against the District because of *93what he believes to be an unconstitutional policy of banning religious music in the District’s public schools. According to Stratechuk, the policy conveys a government sponsored message of disapproval and hostility toward religion (specifically Christianity) and deprives his children of the right to receive information and ideas.
According to the Complaint, prior to the 2004-2005 school year, South Orange-Maplewood allowed religious music in the District’s public schools and permitted children to present religious music — including Christmas music — during curricular and co-curricular activities. That practice changed, however, when the District adopted a strict policy banning all religious music from the public schools. Among other things, the ban purportedly prevents students from learning about, listening to, or participating in the presentation of traditional Christmas music during curricular and co-curricular events such as year-end holiday concerts. Stratechuk further alleges that the policy was implemented to prevent students and student groups from playing traditional Christmas music and conveys the message that Christianity is disfavored.
On March 22, 2005, Stratechuk filed his First Amended Complaint pursuant to 42 U.S.C. § 1983, challenging the constitutionality of South Orange-Maplewood’s policy of banning religious music in the public schools of that district. South Orange-Maplewood filed a motion to dismiss for failure to state a claim under Fed. R. Civ. P. 12(b)(6). Along with its motion, South Orange-Maplewood submitted a copy of the School District’s official policy on religion. Stratechuk objected to the District Court’s consideration of this policy on the ground that it did not reflect the alleged policy and that, because South Orange-Maplewood filed a motion to dismiss and not a motion for summary judgment, the official policy was not properly before the District Court.1
The District Court rejected Stratechuk’s contention and decided that it could consider the official policy without converting South Orange-Maplewood’s motion into a motion for summary judgment because the policy was a matter of public record. After weighing Stratechuk’s allegations and the official policy, the District Court granted South Orange-Maplewood’s motion to dismiss on September 29, 2005. This timely appeal followed.
II. Jurisdiction and Standard of Review
The District Court had jurisdiction over Stratechuk’s 42 U.S.C. § 1983 claim pursuant to 28 U.S.C. §§ 1331 and 1343(a)(3). We have jurisdiction over Stratechuk’s appeal from a final order of dismissal under 28 U.S.C. § 1291.
We exercise plenary review over a district court’s grant of a motion to dismiss for failure to state a claim under Fed. R. Civ. P. 12(b)(6). We are required to consider as true all allegations in the complaint and all reasonable inferences that can be drawn therefrom. Pinker v. Roche Holdings Ltd., 292 F.3d 361, 374 n. 7 (3d Cir.2002) (citing Colburn v. Upper Darby Twp., 838 F.2d 663, 665-66 (3d Cir.1988)). Looking at the facts in the light most favorable to Stratechuk, we must determine whether he can prove any set of facts *94consistent with his allegations that would entitle him to relief. Id.; Hishon v. King & Spalding, 467 U.S. 69, 73, 104 S.Ct. 2229, 81 L.Ed.2d 59 (1984) (citing Conley v. Gibson, 355 U.S. 41, 45-46, 78 S.Ct. 99, 2 L.Ed.2d 80 (1957)).
III. Discussion
The general rule is that a court must accept as true the facts pled in a complaint in ruling on a motion to dismiss for failure to state a claim because such a motion tests the legal sufficiency of the claim and whether the facts as alleged would support relief under the legal theory posited. E.g., Robb v. City of Phila., 733 F.2d 286, 290 (3d Cir.1984) (citations omitted). Under certain circumstances, however, it is permissible for a court to consider matters of “public record” in ruling on a motion to dismiss. PBGC v. White Consol. Indus., Inc., 998 F.2d 1192, 1196-97 (3d Cir.1993). A prerequisite to consideration of an admittedly authentic public document as a part of a motion to dismiss is that the plaintiffs claim relies on that document. Id. at 1196; In re Burlington Coat Factory Sec. Litig., 114 F.3d 1410, 1426 (3d Cir.1997) (holding that the document must be “integral to or explicitly relied upon in the complaint” to be subject to consideration at the motion to dismiss stage) (quoting Shaw v. Digital Equip. Corp., 82 F.3d 1194, 1220 (1st Cir.1996) (emphasis in Burlington Coat Factory Sec. Litig.)).
The District Court determined that it was “without question” that Stratechuk’s complaint was based on South OrangeMaplewood’s official policy. We disagree. At no time in the complaint does Stratechuk quote from the official policy or even mention it. Moreover, the policy Stratechuk describes is more restrictive than the one set forth in the publicly available materials. Perhaps most significantly, when South Orange-Maplewood submitted the official policy with its motion to dismiss, Stratechuk specifically objected on the ground that the facts in his complaint set forth the terms of the policy he was challenging. Thus, even assuming the official policy is a public record, the District Court erred in considering it when ruling on South Orange-Maplewood’s motion to dismiss because the official policy was not “integral to or explicitly relied upon in the complaint....” Burlington Coat Factory Sec. Litig., 114 F.3d at 1426 (quoting Shaw, 82 F.3d at 1220). To the contrary, the policy that Stratechuk alleges was in place in 2004-2005 is decidedly different than the “official policy.”
When, in the context of a motion to dismiss under Rule 12(b)(6), matters outside the pleadings are submitted to a district court and not excluded, the court will sometimes convert the motion to dismiss into a motion for summary judgment pursuant to Fed. R. Crv. P. 56. In re Rockefeller Center Properties, Inc. Sec. Litig., 184 F.3d 280, 287 (3d Cir.1999) (citing Fed. R. Crv. P. 12(b)). This procedural maneuver does not insulate the District Court’s actions here, however, because the District Court expressly declined to convert the motion. Even if the District Court had converted the motion, however, it did so with insufficient notice to the parties and it did not provide Stratechuk with an opportunity to submit materials substantiating his version of the South Orange-Maple-wood policy. See id.
Because a categorical ban on exclusively religious music, enacted with the express purpose of sending a message of disapproval of religion, appears to state a claim under the First Amendment, see Church of the Lukumi Babalu Aye, Inc. v. City of Hialeah, 508 U.S. 520, 532, 113 S.Ct. 2217, 124 L.Ed.2d 472 (1993) (“the First Amendment forbids an official purpose to disapprove of a particular religion or of religion in general”) (citations omitted), we conclude that the complaint would have sur*95vived a motion to dismiss absent the consideration of the extraneous evidence. Accordingly, we will vacate the District Court’s order dismissing the case and we will remand it for further proceedings. On remand, the District Court must afford Stratechuk a chance to show that the policy in place in 2004-2005 is different from the official policy. Once the contours of the relevant South Orange-Maplewood policy are established, South Orange-Maplewood is of course free to test the legal sufficiency of Stratechuk’s First Amendment claim.