Widely hailed as the first science fiction story, A True Story, by Lucian of Samosata is a voyage to the edges of the universe and reason. The title is the first clue that this will be a tall tale. As much a predecessor of Douglas Adams as Jules Verne, Lucian's fantasy explores not only outer space (where he brokers war and peace between the inhabitants of the sun and moon), but also the Elysian fields, the geography of the Odyssey, and the interior of a giant whale. We get to meet Homer, Pythagoras, Socrates, and other immortals, as well as a host of bizarre creatures. The text is riddled with puns, innuendo, parody and satire; however most of this humor will escape the modern reader. Suffice it to say that this was considered pretty funny in the second century C.E. The narrative breaks off in the second book. Whether there were more adventures or Lucian just ran out of ideas is unknown.
This edition includes the English translation of A.M. Harmon, published as part of volume I of the Loeb Classical Library edition of Lucian. It has parallel Greek text on a page by page basis. Each of the two books is about 250 kilobytes, so they may take awhile to load on a slow connection. If you have trouble viewing the Greek text in your browser, you should refer to sacred-texts' Unicode troubleshooting page.
Lucian also wrote another proto-science-fictional piece, Icaromenippus, an Aerial Expedition, available at this site in the Fowler and Fowler translation.