As a second labour he ordered him to kill the Lernaean hydra. That creature, bred in the swamp of Lerna, used to go forth into the plain and ravage both the cattle and the country. Now the hydra had a huge body, with nine heads, eight mortal, but the middle one immortal. So mounting a chariot driven by Iolaus, he came to Lerna, and having halted his horses, he discovered the hydra on a hill beside the springs of the Amymone, where was its den. By pelting it with fiery shafts he forced it to come out, and in the act of doing so he seized and held it fast. But the hydra wound itself about one of his feet and clung to him. Nor could he effect anything by smashing its heads with his club, for as fast as one head was smashed there grew up two. A huge crab also came to the help of the hydra by biting his foot. So he killed it, and in his turn called for help on Iolaus who, by setting fire to a piece of the neighboring wood and burning the roots of the heads with the brands, prevented them from sprouting. Having thus got the better of the sprouting heads, he chopped off the immortal head, and buried it, and put a heavy rock on it, beside the road that leads through Lerna to Elaeus. But the body of the hydra he slit up and dipped his arrows in the gall. However, Eurystheus said that this labour should not be reckoned among the ten because he had not got the better of the hydra by himself, but with the help of Iolaus.
According to Lee, the story would have been inspired by the ancient observation that an octopus can re-grow a severed limb. Additionally, Aristotle knew that octopuses could walk on dry land, and Pliny and Aelian knew that the octopus was capable of feats of great strength, even going to the wharves to crush barrels for a quick meal of the caught fish stored within.
Finally, vase paintings of the hydra bear a distinct resemblance to the octopus.
Of course, the rejoinder to the theory of the octopus as inspiration for the hydra is that the octopus has been known and understood since at least Minoan times (it was a common Minoan artistic motif), raising the question of how an octopus myth could be transformed into a reptile myth.
I suppose the answer to that is Cthulhu.