There are a lot of claimants to the title of inventor of science fiction - Hugo Gernsback, Mary Shelley, and more. But although it hasn't always been seen as a distinct, special sort of fiction, telling stories that incorporate an element of presently-impossible technological achievement and imagining speculative worlds has been part of human civilization forever. Many of the early stories, however, are folklore rather than speculation, and so we don't usually consider them when we discuss the emergence of the genre.
The Iliad describes Hephaestus, the smith-god, forging twenty golden tripods with wheels beneath them, which could "of their own motion" go forth and return to him. These tripods actually fit closely with the first known programmable mechanisms, though the divine version is said to do his bidding and return to him with reports of what they've seen - far beyond the reality, which followed a pre-set path. (These figures were apparently used to enact myths as a sort of sacred drama.) Hephaestus, in other words, had a robot army.
These programmable mechanisms, which simply moved about the stage (apparently often bearing a statue so as to represent some character) without doing anything, were impossibly crude by later standards, so it's no surprise that once many automata were displaying realistic movements including animated facial expressions, the stories get into something closer to artificial life. Eliyahu of Chelm, in the late 16th century, is the first historical figure said to have successfully created a golem, an artificial man made from clay (and very much like a human but lacking the ability to speak), but the notion that they were possible and were made sometimes shows up in Jewish folklore throughout the late middle ages. (The more famous story of the golem of Prague seems to have originated in the 19th century.) Shelley, and later Karel Capek (who first used the word "robot" for artificial men, though the ones in his story aren't mechanical in the way the term has come to mean in modern English - they're more like clones, used as slaves), followed a very long tradition when it comes to the creation of artificial life.
Other themes familiar from science fiction today are also found in folklore. Apparently in Carolingian Lyon, there was a belief in a magical realm, Magonia, located above the clouds, with aerial pirates who raided the realm below and trees whose fruit dropped to earth as hailstones. Fantastic lands of this nature feature regularly in a more explicitly science-fiction type role. One of the earliest examles comes from antiquity; the first-century comic writer Lucian claims to have visited the moon (which was at war with the sun). With the advent of heliocentrism, the idea of life elsewhere in our solar system became popular, and, again, there are many stories of fantastical voyages. The eighteenth-century teller of tall tales Heironymus Karl Friedrich, Baron Münchhausen, is said (although the record of what claims he made is of dubious quality) to have claimed to have ridden a cannon to the moon and met with its king. (The Baron is also said to have pulled himself out of a bog by his own hair, or, in later English versions, his bootstraps, thus giving rise to that particular idiom.)
Until the introduction of scientific reasoning about other worlds similar to Earth, these things belonged to the realm of myth, rather than being seen as imaginative but potentially plausible "what if" stories. It would be centuries beyond that before science fiction came to be regarded as a distinct genre - but many of its roots are in stories told from the earliest days of human society.