Appellant Church of Scientology Flag Service Organization, Inc. (“Scientology”) challenges the district court’s order denying its petition for attorneys’ fees in its civil rights action brought against the appellee, City of Clearwater, Florida (the “City”). The district court’s ruling was based on its determination that Scientology was not a “prevailing party” under 42 U.S.C. § 1988.1 Because we hold that Scientology has met the threshold test for prevailing party status, we vacate the district court’s order.
I. BACKGROUND
In January, 1984, Scientology filed an action under 42 U.S.C. § 1983 to enjoin the enforcement of Clearwater Ordinance No. 3091-83 (the “1983 Ordinance”). The 1983 Ordinance sought to regulate the solicitation of charitable contributions by imposing, inter alia, reporting and record-keeping requirements and prohibiting fraudulent representations. The district court conducted a hearing on a motion for permanent injunction and directed counsel to file post-hearing memo-randa by March 16, 1984.
On March 15, 1984, the City enacted Emergency Ordinance No. 3479-84 (the “1984 Ordinance”), which repealed the 1983 Ordinance in part, but retained many of its provisions. Thereafter, the district court ruled on Scientology’s pending motion to enjoin the repealed 1983 Ordinance. The district court found the 1983 Ordinance facially unconstitutional in its entirety and enjoined its enforcement permanently. On appeal, we vacated that order as moot, reasoning that only the 1984 Ordinance remained in effect. Church of Scientology Flag Serv. Org. v. City of Clearwater, 777 F.2d 598 (11th Cir.1985), cert. denied, 476 U.S. 1116, 106 S.Ct. 1973, 90 L.Ed.2d 656 (1986).
On remand, the district court found the 1984 Ordinance to be constitutional in its *1512entirety.2 Thereupon, Scientology petitioned for attorneys’ fees pursuant to 42 U.S.C. § 1988 on the ground that its earlier litigation triggered the City’s decision to repeal portions of the offending 1983 Ordinance.
Scientology claims to have “prevailed” on allegations that the 1983 Ordinance discriminated against religious organizations, such as itself, that do not conduct regular prayer meetings. The 1983 Ordinance exempted organizations that solicit funds from “members,” defined as “any person regularly attending or participating in a charitable organization.” 1983 Ord. § 100.01(5). To be eligible for the exemption, the 1983 Ordinance required organizations to record and disclose the names of members. Scientology alleged that the exemption had been included at the request of mainline denominations in Clear-water and that the principal purpose of the ordinance was to drive Scientology out of Clearwater. Scientology alleged discrimination in violation of the Free Exercise Clause, unwarranted governmental entanglement with religion in violation of the Establishment Clause, both in violation of the First Amendment to the United States Constitution, and a denial of Equal Protection as guaranteed by the Fourteenth Amendment to the United States Constitution. As a result of these challenges to the limited membership exemption and its disclosure requirement, the provision was repealed by the 1984 Ordinance.
Scientology also challenged a provision granting discretion to the City Attorney, upon receipt of ten citizen complaints, to investigate a charitable organization. Reasoning that only “controversial organizations” such as itself would likely be subject to complaints, Scientology argued that the investigative authority was merely a ruse by which to justify city harassment, unbridled by limits on official discretion. The 1984 Ordinance amended the provision by requiring the City Attorney to investigate upon receipt of ten complaints.3
The 1983 Ordinance, like the 1984 version, required charitable groups to obtain a city permit to solicit funds, imposed a penalty for solicitation without a permit, and authorized judicial review of a decision denying a permit application. Scientology charged that the 1984 Ordinance was overly vague because it did not state whether the penalty could be invoked against an organization that solicited without a permit pending judicial review; if the penalty would have applied in such circumstances, Scientology argued, it would have constituted an improper prior restraint of religious speech. The 1984 Ordinance attempted to pretermit the prior restraint claim by allowing solicitation to continue pending judicial review.
The 1984 Ordinance also eliminated a provision requiring disclosure concerning the tax deductibility of contributions, which Scientology had challenged as discriminatory on its face and as applied. The new ordinance repealed an exemption for organizations soliciting from fewer than twenty members, which Scientology challenged on vagueness grounds, and also clarified other allegedly vague provisions. However, the bulk of the record-keeping and regulatory provisions remained intact.
The district court denied Scientology’s fee request, ruling that it had not “prevailed” because, inter alia, its rights were not vindicated as a result of its lawsuit. Church of Scientology Flag Servs. Org. v. City of Clearwater, 773 F.Supp. 321 (M.D.Fla.1991).
II. STANDARD OF REVIEW
A plaintiff must be a “prevailing party” to recover an attorney’s fee under 42 U.S.C. § 1988. Hensley v. Eckerhart, 461 U.S. 424, 433, 103 S.Ct. 1933, 1939, 76 L.Ed.2d 40 (1983). We review the factual findings underlying a district court’s determination regarding “prevailing party” status for clear error. Fed.R.Civ.P. 52(a); Fields v. *1513City of Tarpon Springs, 721 F.2d 318, 321 n. 7 (11th Cir.1983); Romberg v. Nichols, 970 F.2d 512, 517 (9th Cir.1992); see also Perket v. Secretary of Health and Human Services, 905 F.2d 129, 132 (6th Cir.1990) (“insofar as the district court based its prevailing party determination on a finding that Perket’s lawsuit was the catalyst for the reinstatement of his disability benefits, such a finding is a factual conclusion subject to review for clear error”). Whether the facts as found suffice to render the plaintiff a “prevailing party” is a legal question reviewed de novo. Cf. Nadeau v. Helgemoe, 581 F.2d 275, 281 (1st Cir.1978) (analysis has legal as well as factual component). Once a district court has determined that a party has “prevailed,” its award of attorneys’ fees is reviewed for abuse of discretion. Markham v. International Association of Bridge, etc., 901 F.2d 1022, n. 5 at 1026 (11th Cir.1990); Taylor v. City of Ft. Lauderdale, 810 F.2d 1551 (11th Cir.1987); Solomon v. City of Gainesville, 796 F.2d 1464 (11th Cir.1986). The scope of the district court’s discretion to deny fees to a prevailing party, however, is “exceedingly narrow.” Maloney v. Marietta, 822 F.2d 1023, 1025 (11th Cir.1987).
III. ANALYSIS
It is well-settled that a plaintiff is a prevailing party and thus ordinarily entitled to a fee award of “some kind” if the plaintiff has succeeded on “any significant issue in litigation which achieves some of the benefit the parties sought in bringing suit.” Hensley, 461 U.S. at 433, 103 S.Ct. at 1939 (footnotes omitted), followed, Texas State Teachers Ass’n v. Garland Indep. Sch. Dist., 489 U.S. 782, 791-92, 109 S.Ct. 1486, 1493-94, 103 L.Ed.2d 866 (1989).
[A]t a minimum, to be considered a prevailing party within the meaning of § 1988 the plaintiff must be able to point to a resolution of the dispute which changes the legal relationship between itself and the defendant ... The touchstone of the prevailing party inquiry [therefore] must be the material alteration of the legal relationship of the parties in a manner which Congress sought to promote in the fee statute. Where such a change has occurred, the degree of the plaintiffs overall success goes to the reasonableness of the award under Hensley, not to the availability of a fee award vel non....
Texas State Teachers, 489 U.S. at 792-93, 109 S.Ct. at 1494.
Scientology has met the threshold requirement of “prevailing party” status. It is undisputed that the suit brought by Scientology caused the City to amend the 1983 Ordinance and it is clear that the amendment significantly affected the parties’ legal relationship. The 1984 Ordinance abandoned several challenged provisions, including the limited membership exclusion and the provision providing for unfettered City Attorney investigative and prosecutorial discretion. These successes, while partial only, are neither technical nor de minimis. Id. (citations omitted).
Scientology prevailed on its asserted right not to be treated differently from other religious organizations. The gravamen of its challenge was not that the government may not regulate religious organizations, but that it may not do so in a discriminatory manner that favors one religion over another. See Larson v. Valente, 456 U.S. 228, 244, 102 S.Ct. 1673, 1683, 72 L.Ed.2d 33 (1982). That right was plainly vindicated by the repeal of the challenged limited membership exemption, an action which Clearwater conceded at the time was caused by Scientology’s articulation of alleged constitutional infirmities. See Nadeau, 581 F.2d at 279 (critical inquiry is whether the suit “prompted] defendants to take action to meet plaintiffs claim....”).
The same conclusion applies with similar force to a challenge based upon alleged vagueness. Even if a challenged provision is clarified against the plaintiffs interests, he has succeeded in materially altering the legal relationship in a manner that confers some benefit, namely, the certainty of clearly stated legal norms that bind him. In this case, some of the provisions were clarified in Scientology’s favor, while others were repealed entirely. Cf. Texas State Teachers, 489 U.S. at 792, 109 S.Ct. at 1494 (dictum) (successful challenge of provision as vague might not alone be sufficient to constitute *1514plaintiff as prevailing, especially if provision had never been enforced).
Moreover, it is inappropriate to deny “prevailing party” status merely because Scientology’s pleadings in challenging the amended 1984 Ordinance alleged the same or similar constitutional defects as its earlier action. Scientology’s challenges were addressed to new features of the amended ordinance, as well as old features carried over from the 1983 Ordinance. The fact that Scientology may (or may not) ultimately prevail in those challenges has little do with the question of whether it prevailed in challenging the repealed provisions of the 1983 Ordinance. Scientology did not fail when Clear-water ceased some of its challenged discriminatory conduct merely because the city persisted in other challenged conduct. For this reason, the fact that Scientology challenges the 1984 Ordinance as invalid is irrelevant. As discussed above, there was a material change in the legal relationship between the parties which benefited Scientology, and the fact that Scientology continues to challenge that relationship as modified does not mean that it did not “prevail” as a threshold matter.
IV. CONCLUSION
Scientology’s challenge to the 1983 Ordinance resulted in a material alteration of its legal relationship with the City. It has therefore prevailed for purposes of 42 U.S.C. § 1988. The district court’s order denying the fee award is vacated and the case remanded for a determination of the amount of attorneys’ fees to which Scientology as prevailing party is entitled.
VACATED and REMANDED.
. As amended, 42 U.S.C. § 1988, provides in pertinent part:
In any action or proceeding to enforce a provision of sections 1981, 1982, 1983, 1985, and 1986 of this title, title IX of Public Law 92-318, or title VI of the Civil Rights Act of 1964, the court, in its discretion, may allow the prevailing party, other than the United States, a reasonable attorney’s fee as part of the costs.
. That order is the subject of a separate appeal, Church of Scientology Flag Serv. Org. v. Clearwater, 2 F.3d 1514 (11th Cir.1993).
. Although the language of this provision of the 1984 Ordinance appears somewhat ambiguous, the City concedes that it mandates an investigation upon the receipt of ten complaints, whereas the 1983 Ordinance merely conferred discretion to investigate upon receipt of ten complaints.