The Epic of Gilgamesh (~2500 BCE; here's a fantastic analysis of an original clay edition of Gilgamesh). This is the oldest surviving literary work, and one that contains the seeds of form and tropes spec-fic still uses today. Gilgamesh is the original superhero - his journey and feats largely conform to the "Hero's Journey," and one can find echoes of this work in virtually every piece of fiction written since.
Religious texts such as the Bible, Koran, Mahabharata, Ramayana, and so on (written from ~1400 BCE on). Whether or not you accept one or more of these works as holy writ, the fact is that they are great examples of early fantastic storytelling. Many of the parables and allegories contained therein illustrate common themes, and many of the characters types we use through today first appeared in these works. Like SF, these works usually offer eschatological answers - in a mystical world, mystical answers are as reasonable as scientific ones in our modern world. It goes without saying that these teachings offer a lot of speculative and to think about.
The Iliad and the Odyssey (~700-300 BCE). Epic poetry by Homer - the most famous Hero's Journey - that tell the story of ancient Greece battling ancient Troy. Why consider this SF? Because modern storytelling traces its roots back to these tales, and because these adventure can be rewritten to incorporate metaphor for just about anything.
Aristophanes (~400 BCE). The Clouds and several other works. Additional examples of an author engaging with fantastic elements in a pre-scientific era.
Lucian of Samosata's A True History (200 CE). The first known example of a future history and nascent world-building.
One Thousand and One Nights (~800). Contains storytelling forms and many fantastic elements such as ancient cities, ethereal creatures, mummies, robots, flying craft....
Beowulf (~1000). Many consider this epic poem the first example of English literature - and it's full of monsters!
Dante's The Divine Comedy (1300) takes us to a fully realized alien world (albeit through a form of divine intervention). At least one classic SF novel used it as source material (Inferno, by Niven & Pournelle). In Dante's era, it took major chutzpah to use the word "comedy" in a story about hell.
The Voyages and Travels of Sir John Mandeville (1357 is the likely first publication date), an anonymously published work that draws heavily from the adventures of Marco Polo, with even more fantastic elements. Widely read and translated, this is one of the works that set the stage for SF's "extraordinary journeys" trope that carries on to this day.
Thomas More's Utopia (1516; English translations came later). Introduces the idea of incorporating human society as an object that can be manipulated.
The Chymical Wedding of Christian Rosenkreutz (1616), usually attributed to Johann Valentin Andreae, this story uses the best contemporary understanding of the world (alchemy, which led to modern chemistry) and leaps through time. Originally published in German as Chymische Hochzeit Christiani Rosencreutz anno 1459, this alchemical work is one of three manifestoes of the Rosicrucians, a legendary cult of the era (html version here).
Johannes Kepler's Somnium (written 1593, published 1634). A trip to the Moon, written by the famous scientist, mixing magic and the best astronautical understanding of the time.
A Voyage to the Moon, by Cyrano de Bergerac (published 1656, the year after his death; written in 1649). A whimsical journey to the Moon using the observed effect of rising dew, among other means. His next work, the Comic History of the States and Empires of the Sun, was probably written immediately after the Voyage to the Moon, and published in 1662.
The Description of a New World, Called The Blazing-World, by Margaret Cavendish (1666). Still available in print!
"Micromegas," by Francois Marie Arouet de Voltaire (1752 or earlier). Seminal SF, bringing perspective and humility to the human species by contrasting us with vastly differing sizes of aliens.