Después de estos hechos, arribó a Atenas la nave de Creta que venía a cobrar el tributo debido al rey Minos por la muerte de su hijo Androgeo, causada por Egeo: éste lo había enviado a luchar contra el toro de Maratón y la bestia lo destrozó. Como compensación, el rey cretense exigió que cada nueve años Atenas entregara siete adolescentes e igual número de doncellas como pasto para el Minotauro. Teseo se ofreció para acompañarlos y matar al monstruo, según algunos autores porque se lo pidió Egeo, a instancias de Medea; según otros, él mismo se ofreció voluntario. Egeo despidió a su hijo, pidiéndole que, a la vuelta, la nave llevase velas blancas si estaba vivo y, en caso contrario, que se dejara el velamen negro.
Durante la travesía, según el poeta Baquílides (VI-V a.C.), Minos, que había ido a Atenas a recoger personalmente el tributo, intentó forzar a una de las niñas, pero Teseo se interpuso y para frenar al rey, se declaró hijo de Poseidón. Para comprobar que esto era cierto, Minos lanzó al mar su anillo y pidió a Teseo que se lo trajera. Entonces, dice Baquílides (Ditirambo 17.90 ss.):
"Se estremeció el grupo de jóvenes atenienses después que el héroe saltó al mar, y de sus ojos brillantes como lirios vertían lágrimas, pues esperaban honerosa fatalidad. Más unos delfines, habitantes del mar, llevaban rápidamente al gran Teseo a la mansión de su padre, señor de los caballos; y llegó al palacio de los dioses (…) Vio a la querida esposa de su padre, a la venerable diosa de grandes ojos, en sus amables mansiones, a Anfítrite; ella lo vistió con túnica purpúrea y en sus ensortijados cabellos colocó una impecable corona, que antaño en sus bodas la taimada Afrodita le había dado (…) Junto a la nave de fina popa apareció ¡Pheû! En qué pensamientos frustró al caudillo cnosio, cuando llegó seco del mar, asombro para todos, y brillaban en torno a sus miembros los regalos de los dioses".
Según otra versión, plasmada en la pintura de una copa, Teseo bajó hasta el palacio con la ayuda de un tritón y acompañado por Atenea (fig. 53). Este episodio significa el reconocimiento de la segunda filiación del héroe, que sería hijo de un dios Olímpico al igual que Heracles; sin embargo, la benevolencia de Anfítrite, esposa legítima de Poseidón, contrasta vivamente con la inquina que Hera demostró hacia el hijo de Alcmena (Unidad 3.1; 3.2).
