Opinion by Chief Judge WALLACE; Dissent by Judge PREGERSON.

Kimberly Belshe, Director of the California Department of Health Services (Department), appeals from the district court’s order enjoining it from implementing section 54 of California’s Senate Bill 35, Welfare & Institutions Code § 14132(h) (1993) (Bill 35). Bill 35 restricts the eligibility of patients to be treated for certain dental procedures under Denti-Cal, California’s program for providing dental care to its low-income population. We have resolved the issue of attorneys’ fees in a separate unpublished disposition. Here we address only the question of whether the district court abused its discretion when it enjoined enforcement of Bill 35 on the ground that it violated a previous permanent injunction issued by the court. We have jurisdiction over this timely appeal pursuant to 28 U.S.C. § 1292 . We reverse and remand.

I

In 1965, Congress established the Medicaid program under Title XIX of the Social Security Act, 42 U.S.C. § 1396 , as a cooperative federal-state program to provide medical assistance to the needy. To be eligible for federal financial assistance, participating states must administer their programs in accordance with federal guidelines. California participates in Medicaid through the California Medicaid Assistance Program, commonly known as “Medi-Cal” for medical services, and “Denti-Cal” for dental services.

In 1987, class plaintiffs, made up of individuals who received maternity and dental care under Medi-Cal and Denti-Cal, sued the Department, alleging that they were unable to obtain maternity or dental care because the Department failed to comply with federal Medicaid statutes and regulations. In November 1989, the maternity issues were concluded when the district court approved a consent decree that required the Department to provide written notice before reducing the rates for certain maternity services and to sponsor and support proposed legislation authorizing a single global reimbursement rate for maternity services.

The dental care claim proceeded to trial. In October 1990, the district court held that the Department’s reimbursement rate violated the equal access provision of the Medicaid Act, 42 U.S.C. § 1396a(a)(30)(A). Clark v. Kizer, 758 F.Supp. 572, 575-80 (E.D.Cal.1990) (Clark). The equal access provision requires states to set reimbursement rates at a level sufficient to enlist enough providers so that services are available equally to recipients and to the insured general population within a defined geographic area. The district court found that fewer than 40 percent of the licensed dentists in the state treat any Denti-Cal recipients, and that Denti-Cal recipients have a 32 percent utilization rate, compared to the 67 percent utilization rate for the insured general population.

The district court also concluded that the Department’s policies violated the comparability of services provision of the Medicaid Act, 42 U.S.C. § 1396a(a)(10)(B). Id. at 580. This provision mandates that the medical assistance made available to one recipient shall not be less in amount, duration, or scope than the medical assistance made available to other recipients. Although the district court’s October 1990 judgment resolved the liability aspects of these claims, it deferred determination of the appropriateness of injunctive relief. Id. at 581.

The parties elected to proceed before a magistrate judge on the issue of remedies. The magistrate judge allowed the Department to develop a plan, and it proposed to raise its reimbursement rates for 56 primary care procedures from 40 percent to 55 per *603 cent of the average amount billed by dentists. The magistrate judge rejected this plan because he concluded that the rate would not be sufficient to bring the Department into compliance with federal law, and ordered the Department to raise the rate to 80 percent of average billing. In an unpublished disposition, we affirmed the judgment of liability, and remanded on the issue of the appropriate rate increase.

The magistrate judge conducted an eviden-tiary hearing and concluded that, after one year of experimentation, the 55 percent reimbursement rate did not increase significantly either the number of active providers or the utilization rate. Therefore, on October 15, 1992, the magistrate judge entered an order reimposing the 80 percent reimbursement rate. The order reserved jurisdiction to modify and to enforce the terms of the judgment and to enter further orders on “any matter related thereto.” The order was affirmed on appeal in an unpublished disposition.

In June 1998, the California legislature enacted Bill 35, a law that changed the eligibility requirements of some adult Denti-Cal recipients for certain dental procedures. Bill 35 provides that Denti-Cal will cover certain dental procedures only if the dentist can document a “medical necessity due to a special medical disorder.” Beginning in July 1993, the Department issued a series of bulletins informing dentists of the new law.

On October 29, 1993, plaintiff class filed a motion for an Order of Contempt, Monetary Sanctions and/or Other Remedies. Plaintiff class alleged that the Department’s implementation of Bill 35 undermined the remedial purpose of the district court’s October 15, 1992, injunction to ensure equal access to dental care, and directly violated paragraphs 5 and 7 of the injunction. On December 8, 1993, the Department moved for modification of the injunction to permit the Department to implement Bill 35.

Paragraph 5 of the injunction requires the Department to reimburse participating providers 80 percent of the average amount billed for certain dental procedures. Bill 35 affected eligibility requirements for 14 of these procedures. Paragraph 7 requires the Department to implement Attachment C of the Department’s compliance plan. Attachment C eliminated x-ray submission requirements, prior authorization, and many documentation requirements for certain dental procedures. Bill 35 affected 7 of the 38 procedures listed in Attachment C. The magistrate judge entered an order on December 17, 1993, which was amended on January 24, 1994. In the order, the magistrate judge stated that the language of the injunction was “specific and unambiguous.” He went on to state: “The court declines to find at this time that the defendant is in contempt of the judgment, but will issue the following order to ensure that the express provisions of the judgment are complied with.” The magistrate judge then ordered, among other things, that the Department cease implementing Bill 35 with respect to the procedures listed in the October 15,1992, injunction. The magistrate judge also summarily dismissed the Department’s motion for modification of the injunction as moot.

II

We begin by recognizing that under the Supremacy Clause, U.S. Const, art. VI, § 2, the Department must follow federal law in the face of conflicting state law. It has long been established that “a state statute is void to the extent that it actually conflicts with a valid federal statute” and that a conflict will be found either where compliance with both federal and state law is impossible or where the state law stands as an obstacle to the accomplishment and execution of the full purposes and objectives of Congress. Edgar v. MITE Corp., 457 U.S. 624, 631 , 102 S.Ct. 2629, 2634-35 , 73 L.Ed.2d 269 (1982). Similarly, we have held that “otherwise valid state laws or court orders cannot stand in the way of a federal court’s remedial scheme if the action is essential to enforce the scheme.” Stone v. City and County of San Francisco, 968 F.2d 850, 862 (9th Cir.1992), cert. denied, — U.S. -, 113 S.Ct. 1050 , 122 L.Ed.2d 358 (1993).

The problem here, however, is that there has never been a judicial determination that Bill 35 conflicts with applicable federal law. Due to concerns of comity and federal *604 ism, the scope of federal injunctive relief against an agency of state government must always be narrowly tailored to enforce federal constitutional and statutory law only. Toussaint v. McCarthy, 801 F.2d 1080, 1089 (9th Cir.1986), cert. denied, 481 U.S. 1069 , 107 S.Ct. 2462 , 95 L.Ed.2d 871 (1987). This is critical because “a federal district court’s exercise of discretion to enjoin state political bodies raises serious questions regarding the legitimacy of its authority.” Id. Thus, in reviewing a district court’s injunction against an agency of state government, we scrutinize the injunction closely to make sure that the remedy protects the plaintiffs’ federal constitutional and statutory rights but does not require more of state officials than is necessary to assure their compliance with federal law. Id. We will defer to the district court so long as any injunctive relief it provides remains within these parameters. The district court will be deemed to have committed an abuse of discretion, however, if its injunction requires any more of state officers than demanded by federal constitutional or statutory law. Id.

When the Department made its December 8, 1993, motion for modification of the district court’s injunction, the district court had the option of conducting a hearing to determine whether Bill 35 violated the federal law that the injunction was meant to uphold. Because permanent injunctive relief controls future conduct, federal courts must be sensitive to the need for modification when circumstances change. Id. at 1090 . A sensitivity to the need for modification is particularly important when an injunction involves changing conduct and facts not predicted at the time the injunction was issued. Id. Nevertheless, the district court did not consider the Department’s motion for modification. Instead, the court declared that Bill 35 was inconsistent with the terms of the already existing injunction, and for that reason could not be implemented by the Department.

We hold that the district court was incorrect in its conclusion that Bill 35 was inconsistent with the terms of the existing injunction. Neither paragraph 5 nor paragraph 7 prohibits the Department from changing its eligibility requirements. Rather, these provisions deal with the reimbursement rates and procedures that the Department must follow in order to conform to federal standards.

When the Department is expected to conform its behavior to the injunction or face a contempt sanction, that injunction must be clear enough on its face to give the Department notice that the behavior is forbidden. The class plaintiffs, in seeking to enforce the injunction, must show that the injunction clearly forbids a certain type of conduct. This is why Federal Rule of Civil Procedure 65(d) “requires the language of injunctions to be reasonably clear so that ordinary persons will know precisely what action is proscribed,” and why “all ambiguities are resolved in favor of the person subject to the injunction.” United States v. Holtzman, 762 F.2d 720, 726 (9th Cir.1985) (emphasis added). Cf. Movie Systems, Inc. v. MAD Minneapolis Audio Distrib., 717 F.2d 427 , 432 (8th Cir.1983) (injunction was specific enough to give “explicit notice of precisely what conduct is forbidden”).

The very fact that the magistrate judge felt compelled to issue an order interpreting his injunction belies the suggestion that the injunction on its face clearly prohibited Bill 35. Given that all ambiguities must be resolved in favor of the person subject to the injunction, the holding that paragraphs 5 and 7 are being contradicted by some of Bill 35’s procedures is incorrect. Paragraphs 5 and 7 say nothing on their face about eligibility requirements. Attachment C of the plan, referred to in paragraph 7, does contain a prohibition on “almost all” documentation requirements for some procedures that are covered by Bill 35 and for which Bill 35 requires documentary confirmation of a special medical disorder before the procedure can be performed. However, Attachment C’s paperwork restrictions do not prohibit all documentation. Moreover, requiring a dentist to verify that the patient is eligible for a dental procedure is not necessarily inconsistent with requiring a state to reduce the paperwork required by dentists before the procedure can be performed. After all, the dentist is only authorized to perform the *605 procedure at the state’s expense if the recipient is eligible to receive it. Bill 35’s requirement that an individual demonstrate eligibility for a procedure in the first place is not what Attachment C of the plan was directed at, and its language cannot reasonably be read as such. The language of the injunction does not, on its face, proscribe the implementation of Bill 35.

Because the existing injunction did not clearly prohibit Bill 35, the district court’s order must be considered either a modification of its previous injunction or the issuance of a new injunction. Whatever label is attached to the order, it clearly restricted the actions of state officers without any judicial determination of whether the prohibited conduct — the implementation of Bill 35 — actually violated federal law. The district court’s original judgment of liability contains no determination that Bill 35 violates federal law. See Clark, 758 F.Supp. 572 . The district court made no such determination prior to the issuance or modification of the injunction. This was an abuse of discretion.

United States v. Washington, 645 F.2d 749 (9th Cir.1981), is not to the contrary. There, the district court “enjoined the State of Washington from enforcing a certain statutory program against Indians, on the ground that the program was inconsistent with the rights granted to the Indian tribes by the court’s basic decree.” Id. at 750 . The district court’s “basic decree” involved an interpretation of an Indian treaty. The question before us was: “given the nature of the treaty fishing rights as interpreted by controlling federal decisions and given the effects and operation of the [state program] as described by the district court, [does the state program] have the effect of impairing the Indians’ exercise of their treaty rights?” Id. at 753 . We held that the treaties were “unambiguous” and that the state program had the effect of violating the treaty rights. Id. at 753-74 .

Washington stands for the proposition that a district court can enforce its injunction when: (1) it is based on an interpretation of federal law, (2) the federal law’s purpose and language (in fight of controlling federal decisions including the injunction) is clear, and (3) the effect of the state program being implemented hampers the exercise of that federal law. In the case before us, Bill 35 was held to be inconsistent with the terms of the injunction, not with the federal law upon which the injunction was based. The district court has never concluded that Bill 35 violates federal law. It is irrelevant whether Bill 35 frustrates the broad purpose of the district court’s injunction. It must first be determined whether Bill 35 violates federal law.

The district court’s issuance of its injunc-tive order prohibiting the implementation of Bill 35, without first making a judicial determination that Bill 35 violates federal constitutional or statutory law, clearly constituted an abuse of discretion. The order of the district court prohibiting the Department from enforcing Bill 35 is reversed and the case is remanded to the district court for a determination of whether section 54 of Bill 35 violates federal law and, if so, whether modification of the existing injunction is warranted. We express no opinion on the merits of this issue.

The Department also challenges the scope of the district court’s injunction, arguing that the notice relief ordered by the court violates the Eleventh Amendment. Because we reverse the district court’s order, we do not reach this question.

The class plaintiffs seek attorneys’ fees for this appeal as prevailing parties pursuant to 42 U.S.C. § 1988 . Because they are not prevailing parties, the class plaintiffs are not entitled to fees for this appeal.

REVERSED AND REMANDED.