Theseus en Aegeus waren lange tijd gelukkig, maar bij het begin van de lente werden alle Atheners bedroefd toen een schip met een zwart zeil Athene naderde. Theseus vroeg zijn vader hem te vertellen waarom de Atheners zo bedroefd waren, maar Aegeus wilde niets zeggen.
Theseus ging naar de haven en vroeg de kapitein van het schip met het zwarte zeil wat er aan de hand was. De kapitein vertelde hem hoe de oudste zoon van koning Minos van Creta, Androgeus, per ongeluk in Athene gedood was. Minos was erg boos. Hij viel Athene aan en eiste dat de Atheners hem jaarlijks een schatting van zeven jonge mannen en zeven jonge vrouwen betaald met de bedoeling dat zij te eten gegeven werden aan de Minotaurus. De Minotaurus was half mens en half stier. Hij leefde in het Labyrinth, een grote doolhof waarin een vreemdeling ongetwijfeld zou verdwalen.
Theseus ging terug naar Aegeus en zei, "Ik ga naar Creta als een van de slachtoffers en ik dood de Minotaurus!" "Nee zoon," zei Aegeus, "je mag niet gaan. Je bent mijn enige zoon. De enige erfgenaam voor de troon." "Ik moet gaan, vader. Ik moet bewijzen dat ik een held ben." zei Theseus. Tenslotte liet Aegeus Theseus gaan, maar liet hem beloven dat als hij levend zou terugkeren, hij een wit zeil zou voeren i.p.v. een zwart. Zo ging Theseus als vrijwillig slachtoffer naar Creta.
Toen Theseus en zijn metgezellen op Creta landde, was Minos daar om hen te verwelkomen. Hij vroeg allen wie zij waren. Toen Theseus aan de beurt kwam, zei hij, " Ik ben Theseus, prins van Athene, zoon van Poseidon!" Hierop antwoordde Minos, " Als je de prins van Athene zou zijn, zou de oude Aegeus niet je vader zijn. Om te bewijzen dat je een zoon bent van Poseidon, moet je mijn ring pakken." Minos wierp zijn ring in zee. Terwijl Theseus tot Poseidon bad, dook hij in het water. Hij zag de nimf Thetis die hem de ring en een oude krans gaf. Theseus kwam boven water met de ring en de krans. Minos lachte.
Die nacht werd Theseus bezocht door Minos' dochter Ariadne. Zij zei tegen hem, " Theseus, ik heb besloten om je te helpen de Minotaurus te doden, als je me meeneemt naar Athene en tot vrouw maakt." Theseus was blij met de hulp en beloofde Ariadne dat hij haar zou meenemen. Ze gaf Theseus een bal met zijden draad en zei hem dat hij de draad vast moest binden bij de ingang van het Labyrinth en afwinden als hij het Labyrinth binnenging. De draad zou hem terug naar de ingang brengen.
De volgende dag werden Theseus en zijn metgezellen gedwongen het Labyrinth binnen te gaan. Theseus bond de draad aan een rots en zei zijn metgezellen hem te volgen. Hij leidde hem naar het centrum van het Labyrinth waar de Minotaurus was. Toen zij daar kwamen, zagen zij het beest slapen. Theseus sprong erop en brak een van hoorns af. Theseus begon naar de Minotaurus (die erg boos was) te steken met de hoorn. Toen rende Theseus naar een veiliger afstand en wierp de hoorn als een speer. De hoorn raakte de nek van het monster en bleef daar steken. De Minotaurus deed nu kwaad een uitval op Theseus, maar zakte in elkaar voor hij halfweg was. Iedereen was opgetogen. Theseus was een held! Zij volgden de draad terug naar de ingang van het Labyrinth.
Theseus, Ariadne en de anderen gingen aan boord van het schip met het zwarte zeil en
zeilden naar Athene. Onderweg toen zij op het eiland Naxus overnachtten, kwam de god
Dionysus naar Theseus en zei, "Je mag niet trouwen met prinses Ariadne, want ik
heb haar uitgekozen als mijn eigen bruid. Laar haar hier achter." Theseus deed
precies als de god hem vertelde. Hij was zo bedroefd dat hij vergat een wit zeil te
hijsen. De oude Aegeus zat op een klip op Theseus te wachten, maar toen hij het zwarte
zeil zag, sprong hij in zee. Dat deel van de zee werd naar hem genoemd, de Aegeïsche
zee.