O mar polo que navegaban era o dominio de Poseidón, pero había outras divindades das profundidades acuáticas, especialmente Nereo, o Vello do Mar, coas súas cincuenta fillas coñecidas como as nereidas. Cando Teseo se dirixía a Creta, atopouse cunha destas divindades. O encontro contan que foi así: o rei Minos insinuouse a unha dás doncelas atenienses e Teseo saíu na súa defensa, alegando que era ou seu deber como fillo de Poseidón (Teseo era nunhas versións do mito fillo do rei Exeo, pero en outras fillo de Poseidón). Minos decatouse que a orixe divina de Teseo podía que fose real e ideou a forma de saber se os deuses do mar o axudarían, así que Minos lanzou o seu anel de selo pola borda e desafiou a Teseo a mergullarse e atopalo. O heroe non só recuperou o anel do palacio submarino no que caera, senón que recibiu unha coroa de xoias dunha das nereidas.

Pouco despois de chegar a Creta, Teseo atopou unha aliada na princesa Ariadna, filla do rei Minos. Ela namorouse del á primeira vista.

Foi Ariadna a que lle deu a Teseo unha chave que obtivera do mestre artesán Dédalo. Non obstante, na versión máis estendida da lenda trátase dun nobelo de fío, que ía resultar unha ferramenta inestimable para sobrevivir aos terrores do labirinto.

Dédalo, o arquitecto que deseñara o labirinto, fixera unha obra tan enxeñosa e complicada que unha vez dentro do seu interior, a vítima nunca podería volver atopar a saída. Máis pronto que tarde, el ou ela dobraría unha esquina e atoparíase cara a cara co Minotauro devorador de homes. Este era o destino final que lle esperaba a Teseo.

O Minotauro non era só o monstro do labirinto, senón tamén o seu prisioneiro. Pero non está claro como funcionaba isto na práctica con respecto ás vítimas. Segundo algunhas versións do mito, encerrábaselles no labirinto, coma se fose unha prisión. Pero, seguramente, o procedemento consistía simplemente en empurrar ás vítimas e logo pechar a porta tras elas, que se quedaban xunto á entrada en lugar de penetrar no interior do terrorífico labirinto. Aínda que os gardas ameazásenlles con espadas, parece probable que algúns preferisen a morte por estocada de ferro a ser devorados vivos por un monstro. Os gardas tampouco poderían escoltar ás vítimas ata o máis profundo do labirinto sen perderse eles mesmos ou arriscarse a un encontro co Minotauro. Tal vez Dédalo construíu un teito sobre o seu invento, para que as vítimas puidesen caer por unha porta pequena ata o mesmo centro. En xeral, non coñecemos datos fiables sobre a mecánica do labirinto mitolóxico.

Cando Teseo entrou por primeira vez en tal lugar, atou un extremo do nobelo de fío que lle deu Ariadna, e foi tirando del a medida que avanzaba polas pasaxes labirínticas. Moitos artistas representaron a Teseo matando ao Minotauro coa súa espada ou co seu garrote, pero é difícil ver como podería ocultar armas tan voluminosas na súa roupa. Son máis probables as versións da historia que lle atribúen o encontro co Minotauro cando este durmía e que, de forma heroica, golpéao ata a morte cos seus propios puños. Ou tal vez rompeu un dos cornos da criatura e apuñalouno ata a morte con el. Logo seguiu o fío ata a entrada. Se non fose pola axuda de Ariadna que lle dou o fío, morrería de fame antes de conseguir saír.

Teseo fuxiu con Ariadna, deténdose esta en Creta só o suficiente para furar o fondo dos barcos do seu pai para que non puidese perseguila.

Pero Teseo pronto perdeu á princesa, pois deixou a Ariadna na illa de Naxos; algúns din que abandonada aposta, outros que non sabía que ela desembarcara alí. Ariadna abandonada foi un tema favorito dos artistas ao longo da historia, que se emocionaban ao imaxinar á pobre Ariadna namorada, que deixou familia e benestar polo seu amado e logo remata soa e abandonada nunha illa deserta.

Felizmente, ao final foi rescatada da illa de Naxos nada menos que polo deus Dioniso, que a converteu na súa esposa e, ao parecer, recuperou a felicidade.

Cando o barco que transportaba a Teseo e aos seus compañeiros atenienses liberados se achegaba ao pequeno monte de Atenas no que o rei Exeo, o pai humano de Teseo, vixiaba diariamente o seu regreso, Teseo esqueceu o sinal que acordara co seu pai. As velas da nave só debían ser negras se a expedición concluía como en todas as ocasións anteriores, coa morte dos reféns. O caso e que ben sexa pola alegría de ter conseguido volver, ou ben pola tristeza debido á perda de Ariadna, Teseo esqueceuse de izar unha vela doutra cor, e o rei Exeo lanzouse desde as alturas desesperado polo o que el cría que lle anunciaba a morte do seu fillo Teseo. En conmemoración deste feito, ao mar onde caeu o pai de Teseo déuselle o nome de mar Exeo.