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 seen as having 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 200 years - including Johannes Kepler's 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 - it's author, Kepler himself, was the astronomer who helped lever the earth from the centre of our universe, and Somnium contains the first fruits of this idea: the first 'scientific' description of space journey to observe an alien world and its inhabitants beyond our planet.
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/