Bull

The earliest stories we have of the minotaur, from the Minoan civilization on Crete, are quite different from the story told by Ovid. Even in Ovid's version, the minotaur is simply part bull and part man; the bull-headed man was not a settled image until the Rennaisance. In older stories he was a man with the powerful shoulders, back, and neck of a bull-- a strong giant of a man. He was also said to have been companions with a bull, though unlike Ovid's version the relationship seems to have been one of friendship, similar to the relationship of Gilgamesh and Enkidu. The bull was described as "sky-colored" which has traditionally been interpreted as white, but could also mean blue, as in this sculpture.
The minotaur was a traditional Greek hero similar to Herakles, accomplishing various feats. Hecataeus of Miletus, when describing the ocean as a river encircling the world, recounts that the minotaur traveled on a raft around this river. In another tale, it is said that his words were frozen into solid form as he spoke them, perhaps a reference to the invention of writing.
In Minoan imagery, the minotaur is always associated with a two-headed axe. The island of Crete is largely bare of trees; the minotaur is said to be responsible for clearing the island with his axe.
The Romans called the minotaur "Paulus," meaning small or humble-- an ironic name similar to "Little John" in the Robin Hood myth. The minotaur was usually depicted wearing cloth with a red and black pattern, similar to a checkerboard or a scottish tartan.