ゼウスが生まれ育った島と言われているクレタ島は、エーゲ海周辺で文化が最も栄えた土地だが、テセウスの伝説の中でも最も重要とされるエピソードがある。
ゼウスとテュロスの王女エウロペの間に生まれたミノスがクレタの王位につく前に、己がいかに王に相応しい存在であるかを誇示しようと父ゼウスの兄である、海神ポセイドンに祈り、立派な牛を贈ってくれるように願った。そしてその牛を必ずやすぐにポセイドンの祭壇に捧げるという約束を交わし海底から立派な一頭の牡牛を出してもらった。
しかし、あまりにも見事な牛であったため生贄にすることを勿体無く思い、約束を反故にし別の牛を捧げた。それがポセイドンにバレて罰を下され、妻と牛の間に頭が牛、身体が人間の怪物ミノタウロスを生ませた。これに対し、ミノス王は迷宮を作り、ミノタウロスを閉じ込めた。
アテナイへの旅の途中に彼はマラトンに赴き、その地を荒らしていた凶暴な牛を生け捕りにした。この牛は海神ポセイドンがクレタ島ミノス王に贈ったもので、ヘラクレスがその後、生け捕りにし連れ戻した牛だと言われている。