Για να εδραιώσει τη θέση του στο θρόνο της Κρήτης ο Μίνωας είχε ισχυριστεί ότι οι θεοί θα ικανοποιούσαν όποια χάρη τους ζητούσε στην προσευχή του. Όταν προσευχήθηκε να αναδυθεί ένας ταύρος από τη θάλασσα τον οποίο στη συνέχεια θα θυσίαζε, ο Ποσειδώνας έστειλε ένα εκθαμβωτικό άσπρο ταύρο στην ακτή. Ο Μίνωας θαμπωμένος από την ομορφιά του αποφάσισε να θυσιάσει έναν άλλο ταύρο στη θέση του. Ο Ποσειδώνας προσβλήθηκε και για να πάρει την εκδίκησή του έκανε τη γυναίκα του Μίνωα, την Πασιφάη, να ερωτευτεί τον άσπρο ταύρο. Η Πασιφάη ζήτησε από το Δαίδαλο, ένα διάσημο Αθηναίο τεχνίτη που ζούσε εξόριστος στην Κρήτη, να τη βοηθήσει. Ο Δαίδαλος έφτιαξε μία κούφια ξύλινη αγελάδα στην οποία η Πασιφάη μπορούσε να κρυφτεί και να πλησιάσει τον άσπρο ταύρο. Ο άσπρος ταύρος ζευγάρωσε με την αγελάδα και η Πασιφάη γέννησε το Μινώταυρο, ένα τέρας με κεφάλι ταύρου και ανθρώπινο σώμα. Ο Μίνωας ζήτησε από το Δαίδαλο να χτίσει ένα κτίριο που ονομάστηκε λαβύρινθος, όπου θα έκλεινε το Μινώταυρο.

Μερικοί πιστεύουν ότι ο λαβύρινθος ήταν το παλάτι της Κνωσού. Το καταπληκτικό μέγεθος και η πολυπλοκότητά του δημιούργησαν την ψευδαίσθηση του λαβυρίνθου. Ο ταύρος και ο διπλός πέλεκυς που λεγόταν λάβρυς ήταν τα σύμβολα του μινωικού πολιτισμού και εμφανίζονταν παντού μέσα στο παλάτι.