Heracles was not invented by the Greeks. He was inherited by the Greeks. Half of his labors descend from Mycenaean or Minoan times, implicating a Heracles like figure with a series of labors in the days before Greece was founded. Gilgamesh is a Near Eastern Heracles.
The Greeks adopted the Hero/Labor cycle and transformed it into something substantively Greek. So in that sense Heracles is Greek. Hercules is the Roman adaptation of the Greek Heracles. Though I suppose you could argue that the earliest Romans also had a Heracles like figure in their history, though nothing is known about it if there was. (Or maybe it is right in front of us.)
Quote from my book(pages 300–01)
Heracles was the greatest of Greek heroes, and depictions of his exploits are repeatedly found on Greek vase paintings and art. He was known from the earliest times in Greece, and the numerous mythic motifs about our hero inform us that there lies a far greater context behind his story. There were also numerous and sometimes competing traditions about this Greek figure. Diodorus Siculus identified three separate heroes named Heracles. Servius claimed that there were four separate Heracles, Cicero counted six, and Varro identified forty-four (Smith 401). Herodotus tells us that the original Heracles hailed from Egypt and says that according to the Egyptian tradition, Heracles was one of twelve deities descended from the original eight gods who created the universe (2.43-5). Diodorus claimed that when Osiris went to accomplish his labors he left the government of Egypt in the hands of this primordial Heracles (Smith 401). Remarkably, Pausanias, Tacitus, and Macrobius all confirm that Heracles hailed from Egypt (Smith 401).
To say the original Heracles is Egyptian entirely misses the point. Herodotus also travels to Phoenicia, where he discovers a temple dedicated to the Phoenician Heracles and inside which were two curious pillars, one made of gold and the other of emerald (2.44). Herodotus discovered a similar temple in Tyre dedicated to the Thasian Heracles (2.44). Different sources show that there was a Heracles figure hailing from Crete, Carthage, Libya, India, and even from amongst the Germanic Celts (Smith 401). Several Greek myths derive from the famous labors of Heracles. Theseus performs a series of labors in order to inherit kingship and was known as the Athenian Heracles, Bellerophon was the Corinthian Heracles, and Alcathous was the Megarian Heracles (Nilsson 211-3). Even the Israelites had a Heracles figure in the Biblical Samson.
Details within the myth show the Greeks did not create the story of Heracles—they inherited it. Heracles’ mortal mother’s name is they inherited it. Heracles’ mortal mother’s name is they Mycenaean. King Eurystheus is also Mycenaean, and the kingdom to which he belongs is a Mycenaean city. The localized traditions of our hero in Tiryns descend from Mycenaean times, and the first five labors Heracles performs all take place in the northeastern Peloponnese. The seventh labor, capturing the Cretan Bull, originates in either Mycenaean or even Minoan times (Nilsson 217). In other words, the entire cycle attributed to Heracles is not Greek. Martin P. Nilsson writes, “This idea is pre-Greek. The inference to be drawn from this fact is that a cycle of Labors was already formed and provided with its natural and logical end in the Mycenaean age” (214).