Alors ça va être dur ; un mythe, c'est une histoire ; il faut donc trouver la première trace écrite d'une histoire sans pour autant que cela soit écrit.
Le premier exemple qui me vient à l'esprit, c'est en Mésopotamie ; des mythographes (stade bâtard entre le dessin et l'écriture) racontant ce qui semble être l'histoire d'Etanna ; un roi qui pour assurer sa descendance doit suivre une quête épique impliquant surtout une histoire amusante entre un aigle et un serpent (ils étaient amis, et gardaient les oeufs de chacun, mais un jour l'aigle vorace décide de bouffer les oeufs de son ami ; le serpent pour se venger déplume l'aigle comme un vulgaire poulet et le jette au fond d'un trou ; là arrive Etanna qui redonne des plumes à l'oiseau et s'envole chercher la solution au problème de sa succession en allant voir les dieux).
Après, si on remonte avant, il est diffile de savoir quand on rencontre le motif d'un homme tenant deux lions une préfiguration de Gilgamesh, si les cornes de taureau se réfèrent encore à une histoire, de même que des peintures à çtatal Höyuk ou encore plus loin les grottes de Lascaux.