Minos era fruto dos amores de Zeus com Europa, mas fora criado como filho pelo rei de Creta. Quando este morreu, para conquistar só para si o reino, Minos garantiu aos irmãos, que o disputavam também, que os deuses lho haviam predestinado: para provar que falava verdade, invocou Posídon, pedindo-lhe que fizesse sair do mar um touro que ele, de imediato, lhe sacrificaria. Atendido pelo deus, Minos obteve o trono, mas não cumpriu o prometido, pois achou o touro de tal modo belo que o quis conservar para si. O deus dos mares não tardou a vingar a afronta e tratou de insinuar na mulher de Minos, Pasífae, uma paixão arrebatadora pelo animal. Com a ajuda de Dédalo, o famoso arquiteto, a rainha conseguiu unir-se ao touro e concebeu um filho com corpo humano e cabeça de touro, o Minotauro. Coberto de vergonha e temendo os desmandos daquele ser contranatural, Minos mandou então a Dédalo que construísse um palácio labiríntico onde pudesse encerrar o monstro e donde ele não conseguisse sair.
Para alimentar o Minotauro, Minos decidiu que todos os anos (em outras versões, de nove em nove anos) sete donzelas e sete rapazes de Atenas lhe seriam entregues como pasto: com isso vingava a morte de seu filho Andrógeo, que fora morto pelos Atenienses. No momento do pagamento do tributo pela terceira vez, Teseu, filho do rei de Atenas, ofereceu‑se para seguir no número dos jovens a entregar em sacrifício. Quando chegou a Creta, porém, conquistou o amor de uma das filhas de Minos, Ariadne, a quem prometeu casamento, se ela o ajudasse. A princesa perguntou a Dédalo qual a maneira de o conseguir. Foi, assim, por artimanha dele que ela deu ao herói um novelo (o ‘fio de Ariadne’) e, segundo algumas versões, uma espada mágica. Teseu entrou no Labirinto, foi desenrolando o fio até encontrar o monstro, matou-o e conseguiu depois fazer o caminho de volta à medida que enrolava de novo o novelo. Como castigo pela intervenção do arquiteto, Minos encerrou-o, juntamente com o filho, Ícaro, no labirinto, sem poder, no entanto, prever que a arte e a inteligência de Dédalo lhe permitiriam inventar um modo de se escapar de lá, com as famosas asas de cera.
O Labirinto de Creta identifica-se com o magnífico palácio que ainda hoje podemos visitar nessa ilha grega, testemunho da florescente civilização minoica (3000 a.C.-1100 a.C.).