The formation of Median state, which is dated from the end of the 8th century to the end of 7th century B.C., has become a controversial subject in the ancient Near Eastern studies. The main issue in these studies is the reliability of classical sources, especially Herodotus’ “Mêdikos Logos”, in the reconstruction of Median history which in the recent assessments of state formation in Media, has been questioned because of its apparent contradiction with the cuneiform sources contemporary to the Median period. Present article aims at reassessing the credibility of this narrative in the reconstruction of Median history by reviewing Mêdikos Logos, particularly the foundation of kingship in Media. It seems that, even though, Herodotus has used oral sources for compiling Mêdikos Logos in his Histories, but contrary to some critics, Herodotus’ narrative did not take shape based on epic elements at all. Furthermore, supposed contradictions between Mêdikos Logos and cuneiform sources are partially sketchy. In the other cases, this is due to different approaches between Herodotus and Mesopotamian royal annals about Medes.