Plaintiffs, originally a group of 61 (and now 59) former employees of Kimberly-Clark Corporation, brought a suit for fraud, equitable estoppel, breach of contract, and misrepresentation in Mississippi state court, arguing that Kimberly-Clark had wrongfully denied them severance pay when the corporation terminated their positions on December 31, 2004. Appellees removed the case to federal district court and filed a 12(b)(6) Motion to Dismiss. Plaintiffs filed a Motion to Remand. The district court granted Defendants’ Motion to Dismiss and denied Plaintiffs’ Motion to Remand,1 finding that ERISA preempted Plaintiffs’ claims, and that Plaintiffs had failed to plead that they exhausted their administrative remedies under ERISA and had incorrectly named Kimberly-Clark, rather than the plan administrator, as the defendant.2
Plaintiffs had worked at Kimberly-Clark since January 4, 1982, and alleged that they were entitled to severance pay pursuant to benefits promised in the Kimberly-Clark Hattiesburg Organization Handbook. The Kimberly-Clark Corporation Severance Pay Plan was effective as of January 1, 1998, and provided, as originally written:
Each participant whose employment is involuntarily terminated shall receive Severance Pay; provided, however, that Severance Pay shall not be paid to any Participant who: (a) is terminated for Cause; (b) voluntarily quits or retires; (c) dies; or (d) is terminated as part of a Group Termination ... The Committee [“appointed to administer and regulate the plan] Shall have the sole discretion to determine whether a termination is voluntarily or involuntary, and whether a Participant’s termination is for Cause.
The original plan did not allow for severance pay in the event of “the outsourcing of an Employee to a company other than an Employer” and “a sale or shutdown of a portion of the Corporation.... ” To receive severance pay, employees under the plan were required to complete a Severance Agreement and Release for the Committee. It included a formula for calculating severance benefits and Provided that “[a]ny action on matters within the discretion of the committee ... shall be final and conclusive as to all Eligible Employees and other persons claiming rights under the Plan.” The Kimberly-Clark Board administering the plan amended it on September 10, 2004, to disallow severance pay in the event of “any separation or reorganization of the Corporation including, but not limited to, a sale, spin-off or shutdown of a portion of the Corporation” and “the outsourcing of an Employee to a company other than an Employer.... ”
Because ERISA (29 U.S.C. § 1132(e)(1)) grants the federal courts “exclusive jurisdiction” in civil actions involving ERISA plans,3 the parties dispute whether or not this plan is an Employee Welfare Benefit Plan under ERISA. We do not typically have jurisdiction to review *283a district court’s denial of a Motion to Remand.4 Here, however, because the denial is accompanied by the district court’s granting of the Motion to Dismiss,5 we review de novo the court’s denial of the remand motion6 and find that the district court properly refused to remand plaintiffs’ case to state court on the grounds that it was preempted by ERISA. Although, as Plaintiffs argue, a plan does not fall under ERISA simply because a defendant corporation has called it a “plan,” here a plan existed both in label and in practice. To determine whether ERISA governs a benefit plan, we follow a “three-factor test,”7 asking whether: “(1) the plan exists; (2) the plan falls within the safe-harbor provision established by the Department of Labor; and (3) the employer established or maintained the plan with the intent to benefit employees.”8 To determine the existence of a plan under the first factor, we look to Fort Halifax Packing Co. v. Coyne, 9 which defines the existence of an ERISA benefit plan by an “ongoing administrative scheme” 10 as opposed to a “one-time, lump-sum payment triggered by a single event ... [which] requires no administrative scheme whatsoever.”11 The Supreme Court suggested that “determining the eligibility of claimants, calculating benefit levels, making disbursements, monitoring the availability of funds for benefit payments, and keeping appropriate records in order to comply with applicable reporting requirements” 12 is evidence of an administrative scheme. The pleadings and the discovery ordered by the district judge in determining whether to grant Plaintiffs’ Motion to Remand show that Kimberly-Clark’s plan existed. The Kimberly-Clark Corporation Severance Pay Plan, originally and as amended, set forth specific eligibility criteria that disqualified some potential plan participants. The plan and its amended versions provided increasingly detailed formulas for calculating plan benefits, specified how the payment was to be disbursed, and required its Committee to establish “a procedure for handling all claims.” The original plan also specified the Board’s ability to amend the plan, provided it would not increase the annual cost above a certain amount ($1 *284million or $25 million if approved and executed by the CEO). Although the form of payment under the plan was to be “a lump sum cash payment ... no more than 90 days” following a participant’s termination, this does not negate the existence of a clear administrative scheme governing the plan. Nor does the fact that the company itself formed and operated the plan through a committee diminish the plan’s administrative nature; in Fort Halifax, the court recognized that “an employer that makes a commitment systematically to pay certain benefits”13 and takes on administrative duties such as those described above operates a plan as defined by ERISA. And although some lump-sum severance payment arrangements do not fall under ERISA, those arrangements have involved a discrete payment of one benefit that was not distributed according to a plan.14 Defendant, to the contrary, has shown that it follows specific administrative procedures under a clearly-defined plan in distributing severance benefits. Where other employers have similarly operated severance pay pursuant to a plan— providing the terms in an employees’ handbook and policy manual and setting forth eligibility criteria15—we and other circuits have found that the plan squarely falls under ERISA, despite being funded by an employer’s general resources rather than a specific trust fund.16
Plaintiffs do not contend on appeal that the plan fell within a safe harbor provision. And the plan language itself demonstrates that the plan was intended to benefit employees,17 as do the multiple disbursements that Defendant has made to terminated employees under the plan. Because Plaintiffs failed to show how the severance plan was not a benefits plan under ERISA, the district court properly refused to remand the case to state court.
Plaintiffs next contend that, in granting Defendant’s 12(b)(6) Motion to Dismiss, the court improperly looked beyond the pleadings in finding that Plaintiffs had not exhausted their administrative remedies under ERISA. The court accepted Defendant’s assertion that Plaintiffs had not exhausted their remedies, finding that a plan existed and: “The burden ... rests with the plaintiffs to first allege, then prove if necessary, exhaustion [through the plan] ... Exhaustion is a prerequisite to bringing suit.” 18 Defendant attached a copy of its Severance Pay Plan—the amended version, as of September 10, 2004—to its 12(b)(6) motion to show that the plan was governed by ERISA and therefore required exhaustion of remedies, but Plaintiffs argue that the court improp*285erly considered the plan because it was not authenticated and was outside of the pleadings. We find that the district court properly considered the plan but erred in dismissing the case on the grounds of failure to exhaust administrative remedies.
We review the grant of a motion to dismiss de novo, 19 asking “whether in the light most favorable to the plaintiff and with every doubt resolved in his behalf, the complaint states any valid claim for relief.” 20 We uphold the dismissal “only if it appears beyond doubt that the plaintiff can prove no set of facts in support of his claim which would entitle him to relief.”21 More recently, however, the Supreme Court has established a more stringent pleading requirement, finding that plaintiffs’ “[fjactual allegations [under Rule 8(a)(2) ] must be enough to raise a right to relief above a speculative level”22 and that mere allegations without a suggestion of a loss, for example, and the cause of that loss, are insufficient.23 Appellate courts are “not bound to accept as true a legal conclusion couched as a factual allegation.”24 When granting a motion to dismiss, district courts must limit their review to the pleadings before them.25
With respect to the exhaustion requirement, we have recognized that “ERISA contains no exhaustion requirement whatsoever” 26 but that “we [have] adopted the common law rule that a plaintiff generally must exhaust administrative remedies afforded by an ERISA plan before suing to obtain benefits wrongfully denied.”27 A plaintiff must exhaust his remedies where “the grievance upon which the lawsuit is based arises from some action of a plan covered by ERISA, and ... the plan is capable of providing the relief sought by the plaintiff.”28 More recently, we have more broadly required exhaustion, finding: “A claimant who is denied benefits under an ERISA plan must exhaust all administrative remedies afforded by the plan before instituting litigation for recovery of benefits.”29
Here, Plaintiffs’ pleadings adequately stated a claim for relief. Plaintiffs’ complaint alleged that Kimberly-Clark “represented to each Plaintiff that his or her employment benefits included a right to severance pay” and that they relied upon these representations when they accepted employment with Kimberly-Clark. Further, they alleged that Kimberly-Clark was required to make severance payments within 90 days following Plaintiffs’ termination and “wholly failed to make sever*286anee payments to those plaintiffs.” Wrongful denial of benefits is a cause of action under ERISA § 502(a)(1)(B).30 Because their pleadings were based wholly on a general assertion that Defendant denied them promised benefits,31 without relying upon a reference to the plan, Plaintiffs argue that it was improper for the court to find that they were required to exhaust their administrative remedies under this plan.
Plaintiffs’ contention that the district court should not have considered the severance pay plan in its granting of Defendant’s Motion to Dismiss and determining that Plaintiffs were required to exhaust their administrative remedies under an ERISA plan is without merit. Although district courts “in ruling on Rule 12(b)(6) motions generally may rely only on the complaint and its proper attachments ... [t]hey are permitted to rely on matters of public record.”32 And even if the plan was not part of the public record, the court had already concluded that the plan existed and fell under ERISA when it denied the Motion to Remand. It therefore need not have ignored the plan’s existence in making its determination on the pleadings, particularly because the court had to ascertain whether it had proper jurisdiction over the case, and administrative exhaustion is a prerequisite to jurisdiction under ERISA. Furthermore, Plaintiffs, by avoiding any mention of a “plan” in the proceedings, could not avoid the fact that the very severance benefits they claimed had been wrongfully denied were disbursed pursuant to a plan. Despite the court’s proper consideration of the existence of a plan, however, the court’s requirement that plaintiffs plead exhaustion of remedies under the plan was an improper ground for dismissal here.
Although the complaint fails to allege that Plaintiffs exhausted their administrative remedies, Defendant’s Motion to Dismiss also fails to show how “the plan is capable of providing the relief sought by the plaintiff.”33 Due to the fact that Kimberly-Clark’s plan provides no procedures for appealing the denial of benefits, and that the corporation modified its severance pay plan to explicitly exclude severance pay for termination resulting from spin-off, the plan does not appear to provide any remedies to Plaintiffs. We have “recognized an exception to the affirmative defense of failure to exhaust administrative remedies when such attempts would be futile.”34 Similarly, we have cited the Eleventh Circuit’s finding that “there are occasions when a court is obliged to exercise its jurisdiction ... the most familiar examples perhaps being when resort to administrative remedies is futile or the remedy inadequate.”35 Viewing the facts most favorably to the Plaintiffs, the district court should not have required them to plead exhaustion if any attempt at ex*287haustion would have been futile. Furthermore, as Defendant concedes, the Supreme Court has recently found—with respect to exhaustion requirements under the Prison Litigation Reform Act—that exhaustion is an affirmative defense,36 and that plaintiffs need not “specially plead or demonstrate exhaustion in their complaints”37 to avoid 12(b)(6) dismissal. Although Plaintiffs failed to plead that they exhausted administrative remedies, they need not have done so here.
The district court also erred in finding, when it granted Defendant’s Motion to Dismiss, that Plaintiffs were required to sue the Kimberly-Clark Corporation Severance Pay Plan rather than the corporation itself, relying on Musmeci v. Schwegmann Giant Super Mkts., Inc. 38 In Musmeci, we found that where the employer was both the “plan administrator” and “plan sponsor” and the relevant plan has “no meaningful existence separate from” the employer, it was proper to name the employer as a defendant.39 Plaintiffs’ pleadings alleged that the “Defendant owned and operated a manufacturing facility ... where each of the named Plaintiffs were employed,” that Defendant promised employees severance benefits “orally, in writing, by publication of benefits on a web-site,” and that “defendant discharged each of the 61 plaintiffs and has wholly failed and refused to make severance payments to those plaintiffs.” This evidence, viewed in the light most favorable to the Plaintiffs, could show that suing the plan was unnecessary, as Plaintiffs alleged specifically that the Defendant (not the plan) was responsible for failing to pay the benefits.
We AFFIRM the district court’s denial of Plaintiffs’ Motion to Remand but REVERSE its grant of Defendant’s Motion to Dismiss, REMANDING for proceedings consistent with this opinion.