Although some estimates place the composition of the Avesta well before the Achaemenid period, I know of no physical written documents by Iranians before the Cyrus Cylinder and none in Iranian languages before the Behistun inscription. By that time, the Western Iranians had already diverged into the Persians, Medes, Parthians, and possibly others. Thus, for information about their history before that time, one must rely on neighboring literate cultures for clues - in this case Mesopotamia.
Well into the 12th century BC, written records from the Akkadian-speaking states fail to indicate the presence of any individuals or nations with etymologically Iranian names in the Zagros. The fact that three of the Median tribes Herodotus enumerates don't seem to have Iranian names suggests that prior inhabitants of the region were acculturated by the Iranian newcomers after this time. Unfortunately, political turmoil in Mesopotamia resulted in a period of silence with regards to northern Iran (Kuz'mina, 371-372).
The earliest plausible record of any Western Iranian peoples is the Black Obelisk of Neo-Assyrian king Shalmaneser III, 844 BC, in which the king claims to have received tribute from the 27 kings of Parsua and conquered the Amadai (Butterfield). Amadai may be a form of Media (O.P. Mâda), but Shalmaneser's itinerary appears to place Parsua far to the north of the land known as Parsa in Achaemenid times. Scholars have localized it between the northern border of modern Kermanshah and the south shore of Lake Urmia (Frye, 66).
Assyrian texts also describe a Parsuaš or Parsumaš, which can be localized on the opposite side of Elamite territory from modern Luristan (Gershevitch, 63) and is therefore logical to equate with Achaemenid Parsa. Many historians consider that the initial appearance of Parsua and later Parsumaš indicate the migration of Persians south along the Zagros into their historical territory. Edwin Grantovsky believed that the ethnonyms Parsua and Parsumaš proclaimed "strong" or "broad" people. It has further been observed that a nearby tributary to Shalmaneser III was ruled by an Artasari (Dandamaev and Lukonin, 3-4).
However, Ilya Gershevitch points out that Parsua is always described as a land, not as a people. He argues that Parsua and Parsa, along with the Parsii of Strabo, the Parsyetae of Ptolemy and even the Pashtuns all derive from an Old Iranian term *Parsava, meaning "border[land]." Richard Frye more-or-less concurs, interpreting the root of *Parsava as "rib" but here understood as a frontier, and adds Parthava (Parthia) to the list of cognate borderlands (Frye, 66). It was I.M. D'yakonov's opinion that Parsua and Parsumaš existed simultaneously, reducing the likelihood that one was a colony of the other (Dandamaev and Lukonin, 4)
(In this case, Mâda may well be an Indo-European cognate for "middle." An amusing coincidence, if true: Greek Mēdia means "land of the Medoi [Medes]," but is also the plural of Latin medium, meaning something that is in the middle.)
The questions of whether Parsua can be identified with the Persians and whether it was a migration from the general direction of Parsua (not necessarily colonists from Parsua) that created the settlement of Parsumaš are important insofar as they inform the course of migration. If the answers are yes and yes, then the Persians' ancestors likely followed one of three routes into the northern Zagros Mountains: directly south from the Caucasus region, or northwest across the Iranian Plateau, or west-northwest along the Elborz Mountains. An approach east, through Mesopotamia, is obviously vanishingly improbable, and a further north-northwestern route would require passing through the land that would become Parsumaš only to backtrack and colonize it later, which is not impossible, but seems odd.
If the answer to the first question is no - if Parsua is not connected with the Persians - then alternate routes may be considered: The Persians may then have reached Parsa traveling north-northwest or directly west. If the answer to the first question is yes but the second is no - if Parsua was in fact settled from the general direction of Parsumaš - then alternate routes must be considered, for the same reason that they were so unlikely if Parsumaš was settled from the area of Parsua. However, the likelihood of these is subject to other considerations, as will be seen later.
Anyway, that's as far back as historical records take us. Other evidence is circumstantial. The oldest Iranian compositions are in languages, Old Persian and Avestan, which have already diverged into Western and Eastern (some say Central, or at least non-Western) sub-branches respectively. The earliest Old Persian texts date to. c. 521 BC ("Achaemenid Royal Inscriptions"). The Avestan Gathas are generally thought to be older and might seem to offer a terminus ante quem for the East-West divergence, if its date could be pinned down. Unfortunately, the earliest dates for the life of Zarathuštra come from long after the Achaemenid period and are all over the map, ranging from Diogenes Laertes' six thousand years before Xerxes invaded Greece, to al-Biruni's mere 258 years before Alexander's invasion of Persia (Nigosian, 15-16).
On a possibly-helpful note, the Vendidad, a later Avestan text, does not mention Media, Persia or Parthia. This has been taken by some to mean that the Vendidad was composed before these countries existed (Eduljee), in other words before the eighth and possibly before the ninth century BC (Butterfield).
Obviously, attempting to date the East-West divergence by the composition of the Avesta, and the Avesta by the apparent lack of Western Iranian nations, is somewhat circular. The most that all of points can be taken to imply is that the early Western Iranians took some time after the breakup of proto-Iranian before forming into the nations we know from Assyrian and Classical records. The period may have been quite long.
Archaeologically, the Western Iranians have been tentatively connected with the spread of Late West Iranian buff ware, dating from about 950 BC. This pottery in turn derives from the Gurgan buff ware of c. 1100 BC (Bryant and Patton, 135) which, as its name implies, comes from the area around Gorgan (historically the satrap of Varkâna or Hyrcania). An example of the late type was found at Tepe Sialk VI (Malekzadeh and Naseri) in central Iran. It shows a figure who appears to be bearded, holding a staff or polearm and a checkerboard-patterned rectangular object easily interpreted as a small version of the pavise shield*, and wearing what seems to be an akinakes in a wide-throated scabbard at his waist. In short, he is a direct predecessor of the line spearman of early Achaemenid armies.
If the connection between Western Iranians and the Gurgan buff ware is true, then routes into Media and Persia from anywhere other than the northeast are ruled out. D'yakonov supported the same route on the basis of toponymy (Kuz'mina, 372). This model is also supported by the spread of the Bactrian camel as a livestock animal from east of the Caspian. Like horses below, they were often given ritual burials. West of the Caspian, the use of camels (specifically dromedaries) spread from Arabia and they are known by terms derived from the Phoenician gāmālu, while the Iranian languages maintain native terms, e.g. Avestan uštra (ibid., 377).
Going back to the Vendidad, Hyrcania may appear there under the name Khnentem Vehrkano, while there is no country with a name resembling that of Parthia (whose name, Frye's theory implies, is an artefact of Western Iranian expansion), despite that the two were very close together. I would speculate on the possibility that this could provide a terminus post quem for when Parthia was colonized or terminus ante quem for when the Vendidad was composed, but I can't find sources on whether or when pottery derived from the Gurgan style reached Parthia.
The main competing archaeological model connects Iranian-speakers with wood-framed tombs and horse burials, which may indicate descent from the Srubna or Timber-grave culture that occupied the area directly north of the Black Sea and Caucasus during the Late Bronze Age. This model has the Iranians move almost due south from the Lower Volga through Transcaucasia and into the northern Zagros. It has been observed that the Scythians followed the same route when invading the Near East in the seventh century BC (Kuz'mina, 373-375). Kuz'mina herself concludes that Iranian tribes entered the plateau by both routes (ibid., 378).
This combined model does result in the interesting possibility that Eastern Iranian-speakers entered Iran from the West and Western-speakers from the East, depending on which archaeological culture is associated with which people. In light of the view that the West Iranian buff ware is considered ancestral to Median and Persian pottery, it need not be said that it's simplest to identify its creators with the proto-West Iranians. If that's correct, then the Western Iranians either originated within the Andronovo horizon or passed through there on the way from Srubna areas.
It hardly needs to be pointed out that a material culture isn't necessarily indicative of an ethnolinguistic group; as an obvious example, the early Romans displayed heavy Greek influence in their art, architecture and other material culture without being Greek in origin or adopting the Greek language or identity. So from a theoretical standpoint, it's possible that the Srubna influences and buff ware were simply adopted by Western Iranians as they entered the plateau from elsewhere On the other hand, I can find no alternate model that has scholarly currency.
I am not well-versed enough to try to identify our subject with either the spread of timber graves or buff ware, so it wouldn't be useful for me to arbitrarily voice support one or the other. But in summary the models should look like this:
A) The Western Iranians branch off by around 1100 BC in the area of modern Gorgan and proceed to migrate west along the Elborz into Media and Parsua by the ninth century, south into Persia by the eighth and east into Parthia by the sixth (probably earlier, but not before the composition of the Vendidad, whenever that was).
B) The Western Iranians branch off some time around 1000 BC in the area of southwest Russia and travel southward along the Caucasus. The dates for the settlements of Parsua, Media and Persia are roughly the same as they are in scenario A, but it would make sense for Parthia to be one of the later regions colonized, which more easily allows the possibility of a somewhat later date for the Vendidad.
Both models, such as I understand them, allow for but do not require that the sequential appearance of Parsua and Parsumaš represents the southward movement of Persians over time.
* I would be remiss not to acknowledge that checkerboard-patterned rectangles in isolation are a popular artistic motif on this type of pottery, so the resemblance to a shield may be coincidental.
Adams, Douglas Q. Encyclopedia of Indo-European Culture. Taylor & Francis. 1997.
Bryant, Edwin Francis, and Laurie L. Patton. The Indo-Aryan Controversy: Evidence and Inference in Indian History. Psychology Press. 2005.
Eduljee, K.E. "Aryan Homeland in Avesta." Zoroastrian Heritage. 2005. http://www.heritageinstitute.com/zoroastrianism/aryans/airyanavaeja.htm
Butterfield, Bruce J. "Black Obelisk of Shalmaneser II." Marquette University. 1996. http://mcadams.posc.mu.edu/txt/ah/Assyria/Inscra01.html
Dandamaev, Muhammed A., and Vladimir G. Lukonin. The Culture and Social Institutions of Ancient Iran. Cambridge University Press. 2004.
Frye, Richard Nelson. The History of Ancient Iran. Part 3, volume 7 of Handbuch der Altertumswissenschaft: Alter Orient-Griechische Geschichte-Römische Geschichte. C.H.Beck. 1984.
Gershevitch, Ilya. The Cambridge History of Iran, Volume 2. Cambridge University Press. 1985.
Kuz'mina, Elena E. The Origin of the Indo-Iranians. Koninklijke Brill NV, Leiden. 2007.
Malekzadeh, Mehrdad, and Reza Naseri. "Shamshirgāh and Sialk: bricks with impressions." Antiquity: a review of world archaeology. http://antiquity.ac.uk/projgall/malekzadeh335/
Nigosian, Solomon Alexander. The Zoroastrian Faith: Tradition and Modern Research. McGill-Queen's Press - MQUP. 1993