announced the judgment of the Court and delivered an opinion,
in which Justice Marshat,t,, Justice Blackmun, and Justice Powell join.The question presented by this appeal is whether a preference in civil service employment opportunities offered by the State of New York solely to resident veterans who lived in the State at the time they entered military service violates the constitutional rights of resident veterans who lived outside the State when they entered military service.
*900I
The State of New York, through its Constitution, N. Y. Const., Art. V, §6, and its Civil Service Law, N. Y. Civ. Serv. Law §85 (McKinney 1983 and Supp. 1986), grants a civil service employment preference, in the form of points added to examination scores, to New York residents who are honorably discharged veterans of the United States Armed Forces, who served during time of war, and who were residents of New York when they entered military service.1 This preference may be exercised only once, either for original hiring or for one promotion. N. Y. Const., Art. V, §6.
Appellees, Eduardo Soto-Lopez and Eliezer Baez-Hernandez, are veterans of the United States Army and long-time residents of New York. Both men claim to have met all the eligibility criteria for the New York State civil service preference except New York residence when they entered the Army. Both Soto-Lopez and Baez-Hernandez *901passed New York City civil service examinations, but were denied the veterans’ preference by the New York City Civil Service Commission because they were residents of Puerto Rico at the time they joined the military. Appellees sued the city in Federal District Court, alleging that the requirement of residence when they joined the military violated the Equal Protection Clause of the Fourteenth Amendment and the constitutionally protected right to travel. The Attorney General of the State of New York intervened as a defendant.
The District Court dismissed appellees’ complaint, holding that this Court’s summary affirmance in August v. Bronstein, 417 U. S. 901 (1974), aff’g 369 F. Supp. 190 (SDNY), a case in which a three-judge panel upheld against equal protection and right-to-travel challenges the same sections of the New York State Constitution and Civil Service Law at issue in the instant action, compelled that result. The Court of Appeals for the Second Circuit reversed. Soto-Lopez v. New York City Civil Service Comm’n, 755 F. 2d 266 (1985). It concluded that August, supra, had implicitly been overruled by our more recent decision in Zobel v. Williams, 457 U. S. 55 (1982), and held that the prior residence requirement of the New York civil service preference offends both the Equal Protection Clause and the right to travel. The Court of Appeals remanded with various instructions, including the direction that the District Court permanently enjoin the defendants from denying bonus points to otherwise qualified veterans who were not residents of New York at the time they entered the military service. We noted probable jurisdiction of this appeal of the Attorney General of New York. 473 U. S. 903 (1985). We affirm.
II
“‘[F]reedom to travel throughout the United States has long been recognized as a basic right under the Constitution.’” Dunn v. Blumstein, 405 U. S. 330, 338 (1972) (quoting United States v. Guest, 383 U. S. 745, 758 (1966)). See, *902e. g., Passenger Cases, 7 How. 283, 492 (1849) (Taney, C. J., dissenting); Crandall v. Nevada, 6 Wall. 35, 43-44 (1868); Paul v. Virginia, 8 Wall. 168, 180 (1869); Edwards v. California, 314 U. S. 160 (1941); Kent v. Dulles, 357 U. S. 116, 126 (1958); Shapiro v. Thompson, 394 U. S. 618, 629-631, 634 (1969); Oregon v. Mitchell, 400 U. S. 112, 237 (1970) (separate opinion of Brennan, White, and Marshall, JJ.); id., at 285-286 (Stewart, J., concurring in part and dissenting in part, with whom Burger, C. J., and Blackmun, J., joined); Memorial Hospital v. Maricopa County, 415 U. S. 250, 254 (1974). And, it is clear that the freedom to travel includes the “‘freedom to enter and abide in any State in the Union.’” Dunn, supra, at 338 (quoting Mitchell, supra, at 285).
The textual source of the constitutional right to travel, or, more precisely, the right of free interstate migration, though, has proved elusive. It has been variously assigned to the Privileges and Immunities Clause of Art. IV, see, e. g., Zobel, supra, at 71 (O’Connor, J., concurring in judgment), to the Commerce Clause, see Edwards v. California, 314 U. S., at 173-174, and to the Privileges and Immunities Clause of the Fourteenth Amendment, see, e. g., id., at 177-178 (Douglas, J., concurring). The right has also been inferred from the federal structure of government adopted by our Constitution. Zobel, supra, at 67 (Brennan, J., concurring); Shapiro, supra, at 631; United States v. Guest, supra, at 757-758. However, in light of the unquestioned historic acceptance of the principle of free interstate migration, and of the important role that principle has played in transforming many States into a single Nation, we have not felt impelled to locate this right definitively in any particular constitutional provision.2 Shapiro, supra, at 630. *903Whatever its origin, the right to migrate is firmly established and has been repeatedly recognized by our cases. See, e. g., Hooper v. Bernalillo County Assessor, 472 U. S. 612, 618, n. 6 (1985); Zobel, supra, at 60, n. 6; Jones v. Helms, 452 U. S. 412, 418 (1981); Memorial Hospital v. Maricopa County, supra; Dunn, supra; Shapiro, supra; United States v. Guest, supra, at 757-759.
A state law implicates the right to travel when it actually deters such travel, see, e. g., Crandall v. Nevada, supra, at 46; see also Shapiro, supra, at 629, when impeding travel is its primary objective, see Zobel, supra, at 62, n. 9; Shapiro, supra, at 628-631, or when it uses “‘any classification which serves to penalize the exercise of that right. ’ ” Dunn, supra, at 340 (quoting Shapiro, supra, at 634). Our right-to-migrate cases have principally involved the latter, indirect manner of burdening the right. More particularly, our recent cases have dealt with state laws that, by classifying residents according to the time they established residence, resulted in the unequal distribution of rights and benefits among otherwise qualified bona fide residents.3 Hooper, *904supra; Zobel v. Williams, 457 U. S. 55 (1982); Sosna v. Iowa, 419 U. S. 393 (1975); Memorial Hospital, supra; Dunn v. Blumstein, 405 U. S. 330 (1972); Shapiro, supra.
Because the creation of different classes of residents raises equal protection concerns, we have also relied upon the Equal Protection Clause in these cases. Whenever a state law infringes a constitutionally protected right, we undertake intensified equal protection scrutiny of that law. See, e. g., Cleburne v. Cleburne Living Center, Inc., 473 U. S. 432, 440 (1985); Martinez v. Bynum, 461 U. S. 321, 328, n. 7 (1983); Plyler v. Doe, 457 U. S. 202, 216-217, and n. 15 (1982); Memorial Hospital, supra, at 258, 262; San Antonio Independent School District v. Rodriguez, 411 U. S. 1, 16, and n. 39, 30-32, 40 (1973); Police Dept. of Chicago v. Mosley, 408 U. S. 92, 101 (1972); Dunn, supra, at 335, 342; Shapiro, supra, at 634. Thus, in several cases, we asked expressly whether the distinction drawn by the State between older and newer residents burdens the right to migrate. Where we found such a burden, we required the State to come forward with a compelling justification. See, e. g., Shapiro v. Thompson, supra; Dunn, supra; Memorial Hospital v. Maricopa County, 415 U. S. 250 (1974). In other cases, where we concluded that the contested classifications did not survive even rational-basis scrutiny, we had no occasion to inquire whether enhanced scrutiny was appropriate. Hooper, supra; Zobel, supra. The analysis in all of these cases, however, is informed by the same guiding principle — the right to migrate protects residents of a State from being disadvantaged, or from being treated differently, simply because of the timing of their migration, from other similarly situated residents.4 Hooper, *905supra, at 618, n. 6; Zobel, supra, at 60, n. 6; Memorial Hospital, supra, at 261; Shapiro, supra, at 629-631.
New York’s eligibility requirements for its civil service preference conditions a benefit on New York residence at a particular past time in an individual’s life. It favors those veterans who were New York residents at a past fixed point over those who were not New York residents at the same point in their lives. Our cases have established that similar methods of favoring “prior” residents over “newer” ones, such as limiting a benefit to those who resided in the State by a fixed past date, Hooper, supra; granting incrementally greater benefits for each year of residence, Zobel, supra; and conditioning eligibility for certain benefits on completion of a fixed period of residence, see, e. g., Memorial Hospital, supra; Dunn v. Blumstein, supra; Shapiro, supra, warrant careful judicial review.5 But, our cases have also established that only where a State’s law “‘operates to penalize those persons . . . who have exercised their constitutional right of interstate migration’” is heightened scrutiny triggered. Memorial Hospital, supra, at 258, quoting Oregon *906v. Mitchell, 400 U. S., at 238 (separate opinion of Brennan, White, and Marshall, JJ.).
Our task in this case, then, is first to determine whether New York’s restriction of its civil service preference to veterans who entered the Armed Forces while residing in New York operates to penalize those persons who have exercised their right to migrate. If we find that it does, appellees must prevail unless New York can demonstrate that its classification is necessary to accomplish a compelling state interest. Memorial Hospital, supra, at 262; Dunn, supra, at 342; Shapiro, 394 U. S., at 634.6
*907Ill
A
In previous cases, we have held that even temporary deprivations of very important benefits and rights can operate to penalize migration. For example, in Shapiro and in Memorial Hospital, we found that recently arrived indigent residents were deprived of life’s necessities by durational residence requirements for welfare assistance and for free, non-emergency medical care, respectively, which were available to other poor residents. In Dunn, we held that new residents were denied a basic right by a durational residence requirement for establishing eligibility to vote. The fact that these deprivations were temporary did not offset the Court’s conclusions that they were so severe and worked such serious inequities among otherwise qualified residents that they effectively penalized new residents for the exercise of their rights to migrate.
More recently, in Hooper v. Bernalillo, 472 U. S. 612 (1985), and Zobel v. Williams, 457 U. S. 55 (1982), we struck down state laws that created permanent distinctions among residents based on the length or timing of their residence in the State. At issue in Hooper was a New Mexico statute that granted a tax exemption to Vietnam veterans who resided in the State before May 8, 1976. Zobel concerned an Alaska statute granting residents one state mineral income dividend unit for each year of residence subsequent to 1959. Because we employed rational-basis equal protection analysis in those cases, we did not face directly the question whether *908the contested laws operated to penalize interstate migration. Nonetheless, the conclusion that they did penalize migration may be inferred from our determination that “the Constitution will not tolerate a state benefit program that ‘creates fixed, permanent distinctions . . . between. . . classes of concededly bona fide residents, based on how long they have been in the State.’” Hooper, supra, at 623 (quoting Zobel, supra, at 59). See also Zobel, supra, at 64.
Soto-Lopez and Baez-Hernandez have been denied a significant benefit that is granted to all veterans similarly situated except for State of residence at the time of their entry into the military. While the benefit sought here may not rise to the same level of importance as the necessities of life and the right to vote, it is unquestionably substantial. The award of bonus points can mean the difference between winning or losing civil service employment, with its attendant job security, decent pay, and good benefits.7 Brief for Appellees 27-28. See also Guardians Assn. of New York City *909Police Dept., Inc. v. Civil Service Comm’n, 630 F. 2d 79, 85 (CA2 1980), cert. denied, 452 U. S. 940 (1981); Andrade v. Nadel, 477 F. Supp. 1275, 1279 (SDNY 1979). Furthermore, appellees have been permanently deprived of the veterans’ credits that they seek. As the Court of Appeals observed: “The veteran’s ability to satisfy the New York residence requirement is . . . fixed. He either was a New York resident at the time of his initial induction or he was not; he cannot earn a change in status.” 755 F. 2d, at 275. Such a permanent deprivation of a significant benefit, based only on the fact of nonresidence at a past point in time, clearly operates to penalize appellees for exercising their rights to migrate.
B
New York offers four interests in justification of its fixed point residence requirement: (1) the encouragement of New York residents to join the Armed Services; (2) the compensation of residents for service in time of war by helping these veterans reestablish themselves upon coming home; (3) the inducement of veterans to return to New York after wartime service; and (4) the employment of a “uniquely valuable class of public servants” who possess useful experience acquired through their military service. Brief for Appellant 15. All four justifications fail to withstand heightened scrutiny on a common ground — each of the State’s asserted interests could be promoted fully by granting bonus points to all otherwise qualified veterans. New York residents would still be encouraged to join the services. Veterans who served in time of war would be compensated. And, both former New Yorkers and prior residents of other States would be drawn to New York after serving the Nation, thus providing the State with an even larger pool of potentially valuable public servants.
As we held in Dunn: “[I]f there are other, reasonable ways to achieve [a compelling state purpose] with a lesser burden on constitutionally protected activity, a State may not choose *910the way of greater interference. If it acts at all, it must choose ‘less drastic means.’” 405 U. S., at 343 (quoting Shelton v. Tucker, 364 U. S. 479, 488 (1960)). See also Memorial Hospital, 415 U. S., at 263. Because New York could accomplish its purposes without penalizing the right to migrate by awarding special credits to all qualified veterans, the State is not free to promote its interests through a preference system that incorporates a prior residence requirement.
Two of New York’s asserted interests have additional weaknesses. First, the availability of the preference to inductees as well as enlistees undercuts the State’s contention that one of the most important purposes of the veterans’ credit is to encourage residents to enlist in the services. Second, the fact that eligibility for bonus points is not limited to the period immediately following a veteran’s return from war casts doubt on New York’s asserted purpose of easing the transition from wartime military conditions to civilian life,8 for, presumably, a veteran of the Korean War could take a civil service examination and receive the bonus points tomorrow, 30 years after his homecoming. Cf. Hooper, 472 U. S., at 621. The State’s failure to limit the credit to enlistees recently returned to New York from war strongly suggests that the State’s principal interest is simply in rewarding its residents for service to their country.
Compensating veterans for their past sacrifices by providing them with advantages over nonveteran citizens is a longstanding policy of our Federal and State Governments. See, e. g., Hooper, supra; Regan v. Taxation with Representation of Washington, 461 U. S. 540, 551 (1983); Personnel Administrator of Massachusetts v. Feeney, 442 U. S. 256, 279, n. 25 *911(1979). Nonetheless, this policy, even if deemed compelling, does not support a distinction between resident veterans based on their residence when they joined the military. Members of the Armed Forces serve the Nation as a whole. While a serviceperson’s home State doubtlessly derives indirect benefit from his or her service, the State benefits equally from the contributions to our national security made by other service personnel. “Permissible discriminations between persons” must be correlated to “their relevant characteristics.” Zobel, 457 U. S., at 70 (Brennan, J., concurring). Because prior residence has only a tenuous relation, if any, to the benefit New York receives from all Armed Forces personnel, the goal of rewarding military service offers no support for New York’s fixed point residence requirement.
IV
In sum, the provisions of New York’s Constitution, Art. V, § 6, and Civil Service Law § 85, which limit the award of a civil service employment preference to resident veterans who lived in New York at the time they entered the Armed Forces, effectively penalize otherwise qualified resident veterans who do not meet the prior residence requirement for their exercise of the right to migrate. The State has not met its heavy burden of proving that it has selected a means of pursuing a compelling state interest which does not impinge unnecessarily on constitutionally protected interests. Consequently, we conclude that New York’s veterans’ preference violates appellees’ constitutionally protected rights to migrate and to equal protection of the law.
Once veterans establish bona fide residence in a State, they “become the State’s ‘own’ and may not be discriminated against solely on the basis of [the date of] their arrival in the State.” Hooper, supra, at 623. See also Vlandis v. Kline, 412 U. S. 441, 449-450, and n. 6 (1973); Shapiro, 394 U. S., at 632-633; Passenger Cases, 7 How., at 492 (Taney, C. J., dissenting). For as long as New York chooses to offer its *912resident veterans a civil service employment preference, the Constitution requires that it do so without regard to residence at the time of entry into the services.9 Accordingly, the judgment of the Court of Appeals is
Affirmed.
New York Constitution, Art. V, §6, provides:
“Appointments and promotions in the civil service of the state and of all the civil divisions thereof, including cities and villages, shall be made according to merit and fitness to be ascertained, as far as practicable, by examination, which, as far as practicable, shall be competitive; provided, however, that any member of the armed forces of the United States who served therein in time of war, who is a citizen and resident of this state and was a resident at the time of his entrance into the armed forces of the United States and was honorably discharged or released under honorable circumstances from such service, shall be entitled to receive five points additional credit in a competitive examination for original appointment and two and one-half points additional credit in an examination for promotion or, if such member was disabled in the actual performance of duty in any war... he shall be entitled to receive ten points additional credit in a competitive examination for original appointment and five points additional credit in an examination for promotion. ... No such member shall receive the additional credit granted by this section after he has received one appointment, either original entrance or promotion, from an eligible list on which he was allowed the additional credit granted by this section.”
New York Civ. Serv. Law §85 essentially restates the substance of the constitutional provision and defines the relevant terms.
As was observed in Zobel v. Williams, 457 U. S. 55, 67 (1982) (Brennan, J., concurring):
“[It] is clear from our cases [that] the right to travel achieves its most forceful expression in the context of equal protection analysis. But if, finding no citable passage in the Constitution to assign as its source, some *903might be led to question the independent vitality of the principle of free interstate migration, I find its unmistakable essence in that document that transformed a loose confederation of States into one Nation.”
We have always carefully distinguished between bona fide residence requirements, which seek to differentiate between residents and nonresidents, and residence requirements, such as durational, fixed date, and fixed point residence requirements, which treat established residents differently based on the time they migrated into the State. See, e. g., Martinez v. Bynum, 461 U. S. 321, 325-330 (1983); Memorial Hospital v. Maricopa County, 415 U. S. 250, 255, 267 (1974); Dunn v. Blumstein, 405 U. S. 330, 343 (1972); Shapiro v. Thompson, 394 U. S. 618, 636, 638, n. 21 (1969). As we explained in Martinez:
“A bona fide residence requirement, appropriately defined and uniformly applied, furthers the substantial state interest in assuring that services provided for its residents are enjoyed only by residents. Such a requirement . . . [generally] does not burden or penalize the constitutional right of interstate travel, for any person is free to move to a State and to establish residence there. A bona fide residence requirement simply requires that *904the person does establish residence before demanding the services that are restricted to residents.” 461 U. S., at 328-329.
Of course, regardless of the label we place on our analysis — right to migrate or equal protection — once we find a burden on the right to migrate the standard of review is the same. Laws which burden that right must *905be necessary to further a compelling state interest. See, e. g., Memorial Hospital, supra; Dunn, supra; Shapiro, supra.
We have cautioned, however, that not all waiting periods are impermissible. See, e. g., Memorial Hospital, supra, at 258-259; Shapiro, supra, at 638, n. 21. Indeed, in Sosna v. Iowa, 419 U. S. 393 (1975), we upheld a 1-year residency condition for maintaining an action for divorce. We noted the State’s strong, traditional interest in setting the terms of and procedures for marriage and divorce. Weighing the fact that appellant’s access to the desired state procedure was only temporarily delayed, against the State’s important interest, we concluded that her right to migrate was not violated.
We have also sustained domicile requirements, which incorporated 1-year waiting periods, for resident tuition at state universities. Starns v. Malkerson, 401 U. S. 985 (1971), summarily aff’g 326 F. Supp. 234 (Minn. 1970) (three-judge court); Sturgis v. Washington, 414 U. S. 1057 (1973), summarily aff’g 368 F. Supp. 38 (WD Wash.) (three-judge court). See also Vlandis v. Kline, 412 U. S. 441, 452-454 (1973).
In his concurrence, The Chief Justice takes us to task for asking in the first instance what is the appropriate standard of review to employ in evaluating New York’s laws. The Chief Justice argues that we should initially run the laws through a rational-basis analysis and then, if they survive that level of scrutiny, ask whether a higher level is appropriate.
We disagree. The logical first question to ask when presented with an equal protection claim, and the one we usually ask first, is what level of review is appropriate. See, e. g., Dunn, 405 U. S., at 335 (“In considering laws challenged under the Equal Protection Clause . . . [f]irst... we must determine what standard of review is appropriate”). See also, Cleburne v. Cleburne Living Center, Inc., 473 U. S. 432 (1985); Mississippi University for Women v. Hogan, 458 U. S. 718 (1982); Plyler v. Doe, 457 U. S. 202 (1982); Memorial Hospital v. Maricopa County, 415 U. S. 250 (1974); San Antonio Independent School District v. Rodriguez, 411 U. S. 1 (1973); Police Dept. of Chicago v. Mosley, 408 U. S. 92 (1972); Shapiro v. Thompson, 394 U. S. 618 (1969). It is well established that where a law classifies by race, alienage, or national origin, and where a law classifies in such a way as to infringe constitutionally protected fundamental rights, heightened scrutiny under the Equal Protection Clause is required. See, e. g., Cleburne, supra, at 440; Martinez, 461 U. S., at 328, n. 7; Plyler v. Doe, supra, at 216-217, and n. 15; Memorial Hospital, supra, at 258, 262; San Antonio Independent School District, supra, at 16, and nn. 39, 30-32, 40; Mosley, supra, at 101; Dunn, supra, at 335, 342; Shapiro, supra, at 634. In the instant case, appellees contend not only that the laws in question treat them differently from another class of state residents, they also maintain that by treating them differently, the laws burden their constitutionally protected right to travel. Therefore, in order to ascertain the ap*907propriate level of scrutiny, we must, as an initial matter, determine whether or not the State’s laws actually burden appellees’ right to travel.
It is true, as The Chief Justice suggests, that in Hooper v. Bernalillo County Assessor, 472 U. S. 612 (1985), and Zobel v. Williams, 457 U. S. 55 (1982), the Court did not follow this same logical sequence of analysis. We think that the better approach is that which the Court has employed in other equal protection cases — to inquire first as to the proper level of scrutiny and then to apply it.
In Andrade v. Nadel, 477 F. Supp. 1275, 1279 (SDNY 1979), the Deputy Director of the New York City Department of Personnel testified:
“[O]n most civil service examinations, there is a pronounced ‘bunching’ (i. e., a large percentage of the test takers obtain very similar scores). [I]t can be assumed that rescission of the five or 10 point veterans’ preference in the case of most of 1,300 employee [veterans receiving probationary appointments in New York City in a specific year would] result in their receiving a list number that has not yet been reached for appointment, and . . . consequently [in their losing] their jobs.”
Appellees contend that this “bunching” phenomenon adversely affected their employment opportunities with the City of New York. For example, after passing a New York City civil service examination, Baez-Hernandez was preliminarily awarded 10 veterans’ bonus points — 5 for veteran status, and 5 for his service-related disability, bringing his total score to 87.3. Based on this adjusted score, he received an appointment with the city in June 1981. The award of the 10 bonus points was rescinded two days later, however, and the appointment withdrawn when it was discovered that Baez-Hernandez was not a New York resident at the time of his entry into the Army. Soto-Lopez v. New York City Civil Service Comm’n, 755 F. 2d 266, 268-269 (CA2 1985).
Moreover, it is difficult to understand why veterans who joined the military as New York residents would have so much more trouble effecting this transition than other veterans that New York is justified in reserving “the benefits [it] bestows for national military service” for only one class of resident veterans. Hooper v. Bernalillo County Assessor, 472 U. S., at 621.
Our summary affirmance in August v. Bronstein, 417 U. S. 901 (1974), is hereby overruled.