Критский бык, которого когда-то изловил, а потом и выпустил Геракл, шатался близ Марафона, сея хаос. Желая помочь афинянам, Тесей выследил его, изловил и принес в жертву Аполлону.

Однако Марафонский бык, как стали называть переселившегося Критского быка, был для Афин мелкой неприятностью по сравнению с ужасной данью, которую город вынужден был выплачивать Миносу, царю Крита, регулярно отправляя ему семь юношей и семь девушек на съедение Минотавру.

Минотавр, свирепый монстр с телом человека и головой быка, был заточен в запутанном лабиринте и время от времени питался импортными афинянами.

Тесей отважно присоединился к группе обреченных молодых людей, плывших на Крит. Когда Минос стал приставать к одной из девушек, Тесей вступился за нее, а на притязания царя, мнившего себя сыном Зевса, заявил, что ни в чем ему не уступает, ибо он сын Посейдона. Минос немедленно подтвердил свое божественное происхождение, воззвав к Зевсу и получив от него отрадный раскат грома. Затем, бросив в море кольцо, он попросил Тесея вернуть ему его и тем подтвердить свое происхождение. Тесей храбро прыгнул в пучину, где его радушно встретила жена Посейдона, Амфитрита.

С помощью влюбившейся в него Ариадны, дочери Миноса и Пасифаи, Тесей убил Минотавра и вместе с другими юношами и девушками выбрался из лабиринта. По пути домой беглецы причалили к острову Наксос, а когда отправились дальше, обнаружили, что «забыли» Ариадну. Есть несколько объяснений, почему Тесей бросил свою благодетельницу, согласно самому благочестивому из них, это произошло по чистой случайности. В конце концов для Ариадны это обернулось большой удачей, поскольку одинокую и оставленную в беде красавицу нашел бог Дионис, и он так воспылал к ней любовью, что не только женился на ней, но и наградил ее бессмертием.

Полный эйфории от своего победоносного возвращения в Афины, Тесей забыл, что обещал отцу в случае успеха сменить обычные черные паруса на белые (или алые). Эгей, увидев приближающийся корабль под черными парусами, в отчаянии кинулся в море, которое с тех пор называется в его честь Эгейским.

Таким образом, Тесей стал правителем Афин. По более поздним преданиям, он объединил всю территорию Аттики в единое государство, провел демократические реформы и проявлял сострадание к просителям, даже если помощь им таила в себе опасность. Но он часто отсутствовал. Отправился в страну амазонок (возможно, вместе с Гераклом) и сражался с ними, а одну похитил, и она родила ему сына Ипполита. Чтобы ее вернуть, амазонки осадили Афины, но потерпели поражение.