Il mito del minotauro inizia a Tiro, città di cui era re Agenor, figlio di Poseidone e della mortale Libia.
Poseidone si sposò Libia e da questa unione nacque Europa, una fanciulla particolarmente bella e pura di cui Zeus s'innamorò perdutamente.

Da questa unione nacquero tre figli. Uno di questi era Minosse, famoso per la sua severità e giustizia, che regnò su Creta e e fu signore del mare.
Minosse chiese a Poseidone, dio del mare, di mandargli un toro. Ricevere questo toro dal dio era la prova che l'Olimpo approvava il suo regno. In effetti, Poseidone mandò il toro, un toro di un bianco stupefacente, destinato ad essere sacrificato. Ma Minosse affascinato dalla sua bellezza non lo sacrificò; la sua forza era tale che il re di Creta, pieno di ammirazione, decise di utilizzarlo come toro da monta per i suoi greggi.

Quando Poseidone lo venne a sapere, al fine di punire Minosse, non solo convertì il bel toro in un animale pericoloso ma fece anche in modo che Pasifae, moglie di Minosse, s'innamorasse del toro e si unisse a lui. Fu da questa unione che nacque il Minotauro, un mostro con il corpo di uomo e la testa di toro. Un mostro pericoloso e al tempo stesso di così alta stirpe, un pericolo da scongiurare che minacciava la pace ed il benessere del regno. Così Minosse lo rinchiuse in un palazio la cui costruzione affidò ad un architetto ateniese di nome Dedalo il quale, iniziato da Atenea a tutte le invenzioni dell'arte e dell'industria, costruì un palazzo a forma di labirinto - il labirinto di Cnosso: doveva essere un inestricabile susseguirsi di camere, corridoi, sale, finti ingressi e finte porte, un luogo dove perdersi e da cui fosse impossibile uscire.

Più tardi,anche l'ateniese Dedalo vi fu rinchiuso col figlio Icaro, e poté fuggire soltanto costruendosi delle ali fatte di penne e cera inventando così l'arte del volo. Racconta la leggenda che Icaro volò tropo vicino al sole, le ali si sciolssero ed egli cadde in quel mare, che presumibilmente da lui fu chiamato Icario. Soltanto Dedalo si salvò.

Il figlio di Minosse, Androgeo, giunse ad Atene per misurarsi con i giovani ateniesi nei giochi tauromachici, ma rimase ucciso dal toro di Maratona. Suo padre, pazzo di dolore, si strappò la corona dalla fronte accusando gli ateniesi di quell'omicidio, la morte di Androgeo doveva portare loro sfortuna e da lì in poi dovettero pagare un orribile tributo: ogni nove anni Minosse esigeva che mandassero a Creta quattordici sudditi ateniesi, sette fanciulli e sette fanciulle vergini in pubertà, che sparivano nel labirinto sacrificate al Minotauro.

Quando Teseo vinse il toro di Maratona, erano già passati diciotto anni e Minosse stava per scegliere, per la terza volta, la schiera del sacrificio. Secondo la narrazione più antica, Teseo sarebbe andato a Creta con la sua nave o con quella di suo padre per evitare un'altro inutile sacrificio, ossia per uccidere il minotauro. Era partito con le vele nere ma suo padre gliene aveva data anche una bianca che avrebbe dovuto essere issata se Teseo fosse ritornato vittorioso.

In tutte le narrazioni, Teseo fu ricevuto a Cnosso da una figura di donna gentile, forse una dea come Anfitrite.
Ma quando questi volle entrare spontaneamente nel labirinto, Arianna (nipote di Elio e Zeus, figlia di Minosse e Pasifae), signora del labirinto, ebbe pietà di lui e, per amore del giovane ateniese, tradì il proprio fratello, il Minotauro. Non ci sono narrazioni di come Teseo riuscì ad ottenere il dono da Arianna, che doveva assicurargli l'uscita dal labirinto; un disegno molto antico la rappresenta filando e mentre gli consegna il fuso col filo. L'astuta ragazza sugerì a Teseo di fissare il capo del filo all'architrave dell'entrata del labirinto e di tenersi il gomitolo in mano senza perderlo mai, poiché gli sarebbe servito a trovare la via di uscita.

Il Minotauro dormiva nella parte più interna del labirinto. Teseo doveva afferrarlo per le sopracciglia e sacrificarlo a Poseidone. Con una mano si afferrarono a vicenda, e infine Teseo trafisse mortalmente il Minotauro. Egli appare vittorioso alla porta dell'edificio sotterraneo senza portare con se il Minotauro ucciso, dove viene accolto festosamente dai fanciulli ateniesi scampati al sacrificio.

Teseo salì sulla nave con Arianna e durante la notte presero la via del ritorno, portando con sé anche i giovani ateniesi. Teseo aveva promesso di corrispondere all'amore di Arianna sposandola una volta vinto il Minotauro. Consumarono il loro amore nella nave, ma prima dell'alba Teseo volle scendere a terra, e sbarcarono nell'isola di Dia, l'attuale Nasso. Dioniso apparve in sogno a Teseo e lo minacciò se non gli avesse ceduto Arianna. Egli si svegliò spaventato e la lasciò sull'isola immersa nel sonno. Quella stessa notte ella fu portata da Dioniso sul monte Drios, e scomparvero entrambi.

Teseo proseguì con i giovani in direzione di Delo, dove ballò una danza che imitava le sinuosità del labirinto. Ma nella confusione di emozioni per la perdita di Arianna, si dimenticò di cambiare le vele nere con quella bianca. Egeo che attendeva il ritorno del figlio dall'alto delle mura, vide dall'Acropoli le vele nere che la nave portava alla partenza. Così, scorgendo quel segno di sventura, disperato, si uccise gettandosi in quel mare che da lui prese il nome.