Kojarzy się go przede wszystkim z Minotaurem, choć dla starożytnych Greków pokonanie potwora nie było najważniejszym czynem tego herosa. Już w epoce antycznej określano go mianem drugiego Heraklesa, będącego notabene jego kuzynem. Dla Ateńczyków okresu klasycznego był przede wszystkim herosem założycielem, któremu przypisywano synojkizm – zjednoczenie Aten w jeden organizm państwowy, stworzenie fundamentu potęgi tego polis. W świecie starożytnym postrzegano go zatem jako czczonego ojca ateńskiej wspólnoty oraz bohatera licznych przygód.
Wokół Tezeusza narosło wiele narracji, które rzadko układają się w spójną, linearną historię. Narodziny herosa miały wyjątkowy charakter. W poszukiwaniu problemu bezdzietności Ajgeus, król Aten, udał się po wyrocznię do Pythii. Nie zrozumiawszy jej słów, zwrócił się do Pitteusa, króla Trojzeny, który odczytawszy sens przepowiedni, doprowadził do współżycia gościa ze swoją córką Ajtrą. W innym wariancie mitu Ajtra – za namową Ateny – udała się na pobliską wyspę, gdzie obcowała z Posejdonem. Tezeusz miałby więc dwóch ojców: ludzkiego i boskiego.
Ajgeus, obawiając się, że jego brat będzie nastawać na życie jego syna, pozostawił dziecko w Trojzenie. Ojcowski miecz i sandały spoczęły pod głazem do czasu, aż dorastający Tezeusz zyska siłę, by je wydobyć. Gdy tylko odsunął kamień i przejął ojcowskie pamiątki, ruszył w pełną niebezpieczeństw drogę do Aten.
Mając do wyboru dwie drogi, wybrał trudniejszą, lądową, która pozwoliłaby mu osiągnąć sławę podobną do heraklesowej. Zabiwszy swojego pierwszego przeciwnika, Perifetesa, odebrał mu jego maczugę i uczynił ją swoją własną bronią. Następnie pokonał Sinisa, zwanego zginaczem sosen (mordował podróżnych, rozrywając ich za pomocą dwóch drzew bądź wystrzeliwując z ich wierzchołka).