Lucian's True History describes a voyage to the moon by a ship lifted up in a waterspout, but it soon abandons this science fiction idea for a farce, with descriptions of battles between the vegetable armies of the warring Kingdoms of the Moon and Sun standing for the 'histories' of writers such as Herodotus, whom Lucian is mocking: "and it's all absolutely true" being the punchline.
The Arabian Nights and even earlier sources - including Homer and the Vedas - are sometimes said to have science fiction elements, or contain story ideas that have been recycled by science fiction authors over the years, but since they predate the development of science itself maybe they should be called pre-scientific or pre-science fiction.
Mary Shelley's Frankenstein comes too late, in the 1810s, when literature describing fantastic "scientific" & philosophical explorations has been around for more than 200 years - including the Somnium in about 1608.
The Somnium is the earliest possible candidate to be the first science fiction story since the early scientific period in Europe - after all it was written by Kepler, the astronomer who would go on to lever the earth from the centre of our universe.
You can read a new English translation of Kepler's Somnium at http://somniumproject.wordpress.com and follow @SomniumProject on twitter for line-by-line tweets from the full text of the story. More on the origins of Kepler's Somnium and other early science fiction: http://somniumproject.wordpress.com/faq/