Eurystheus having seen Hercules bringing Diomedes
Mares, he remained speechless, and was thinking of
what will be his next labor... and he found it.

  -  Hercules, you are to go to the island of Crete,
and you will bring me the wild bull of king Minos.

(Some say that this is the bull that ferried Europa to Crete, and others say that it was the bull that the god of the sea Poseidon sent up from the sea to king Minos).

Goddess Hera was watching Hercules close, and she was the one that was choosing the labors for Hercules and speaking through Eurystheus. She believed that this time Hercules will flinch and will refuse to face the bull of Poseidon. But she was wrong.

  -  Well, Eurystheus asked Hercules, looking at him standing there without saying anything.
  -  Have you flinched and you don't want to carry out this labor?
  -  I have not flinched at all, said Hercules. I was only thinking which way to capture the bull. I'm on my way to Crete.

But what was this bull?

King Minos was the ruler of Crete those days, and one day as he was gazing at the sea he made a very strange thought.
  -  If I am to see something coming out from the sea, I will sacrifice it to its god Poseidon. Just as he made this thought, a magnificent black bull was to be seeing coming out of the water. King Minos was feel with admiration for the animal. Such a beautiful and strong bull was never seeing before.

  -  Such a pity to sacrifice such a wonderful animal, he thought, forgetting his promise to the god.
  -  I will keep him and sacrifice another bull instead.

Poseidon was very mad with King Minos not keeping his promise, and made the bull get wild and run into the nearby forest. From that day on this bull was to be the fear and terror of Crete, killing any living creature that crosses its way.
It's been also said that the legendary Minotaur that was killed by another great Greek hero later on, Theseus, was the son of this horrible bull.

This wild bull, Eurystheus commanded Hercules to capture, tame,
and bring back to Tiryns.

After a long journey, Hercules arrived in Crete. He requested aid from the king, but he told him to fight the bull for himself.

Hercules waited the horrifying bull in one of its paths.
As soon as he saw the bull coming out of the forest attacking him with his horns, Hercules with a quick movement cast his rope and manage to pass it over its head and one leg. The beast fell on the ground giving just enough time to Hercules to hit it on the head with his mighty club.
The beast got dizzy, so he tied on the animal with ease.
Then Hercules carried the bull on his back and onto a ship and brought it back to Eurystheus.

The bull was then set free by Eurystheus. It wondered for a while in Peloponissos and then went on to Attica where he spread fear and death again, until another great Greek hero came on to kill it.