Archeolodzy i historycy twierdzą, że Efez został założony jako kolonia attycko-jońska w X wieku p.n.e. na wzgórzu znanym dziś jako Ayasuluk, około trzech kilometrów od późniejszego centrum starożytnego miasta. Wykopaliska prowadzone w latach 90. XX wieku na terenie zamku w Selçuku potwierdziły istnienie tej wczesnej osady, odsłaniając fragmenty ceramiki i umocnień charakterystycznych dla wczesnej kultury jońskiej. A jednak, jak często bywa w przypadku miast, które żyją nie tylko w kamieniu, lecz także w pamięci, istnieje bardziej poetycka opowieść o narodzinach Efezu — ta, którą przekazali nam starożytni pisarze, tacy jak Pauzaniasz i Strabon.

Według tradycji greckiej założycielem Efezu był Androklos, odważny i żądny przygód syn Kodrusa, ostatniego legendarnego króla Aten. W czasach, gdy stary świat drżał pod naporem Dorów — około 1070 roku p.n.e. — Peloponez płonął od wojen. Dorowie, zahartowani w boju i prowadzeni ambicją, przemierzali Grecję, zostawiając za sobą upadłe królestwa i zmieniające się granice. Ich wódz, Aletes, syn Hipopotesa, zapragnął zdobyć same Ateny — starożytne miasto mądrości i odwagi. Zanim jednak ruszył do ataku, zwrócił się, jak wielu przed nim, do wyroczni delfickiej, by poznać wyrok losu.

Wyrocznia przekazała przepowiednię prostą, lecz okrutną: inwazja Dorów zakończy się sukcesem, dopóki król Aten pozostanie nietknięty. Była to zarazem obietnica i ostrzeżenie — a w tamtych czasach słowa płynące z Delf miały moc równą prawom bogów. Gdy wieść o przepowiedni dotarła do Aten, wkrótce usłyszał ją król Kodrus, ostatni z rodu Kekropsa. Natychmiast zrozumiał jej znaczenie. Wiedział, że jego lud nie ma szans powstrzymać doryckiej potęgi siłą oręża — jedynym ratunkiem mogła być jego śmierć. I tak król postanowił uczynić coś, na co mało który władca w historii się zdobył: poświęcić własne życie, by ocalić swoje miasto.

Przebrany w szaty wieśniaka, Kodrus wymknął się poza ateńskie mury i przekroczył rzekę, która oddzielała jego miasto od obozu wroga. Tam, wśród żołnierzy Dorów, zaczął ich prowokować — wyśmiewał, rzucał obelgi, aż w końcu wywołał bójkę. Walka była krótka. Jeden z wojowników ugodził go mieczem, i Kodrus padł — nie jako król na tronie, lecz jako bezimienny człowiek. Kiedy Dorowie zorientowali się, kogo zabili, ogarnął ich strach. W uszach dźwięczały im słowa wyroczni: ich zwycięstwo zależało od bezpieczeństwa króla. Teraz, gdy Kodrus nie żył, boska obietnica została złamana. Przerażeni gniewem Apollina i klątwą Delf, porzucili wyprawę i wycofali się, zostawiając Ateny nietknięte.

Po tych wydarzeniach rozpoczął się nowy rozdział w historii Aten. Cześć dla ofiary Kodrusa była tak wielka, że żaden człowiek nie śmiał już zasiąść na jego tronie. Ateńczycy ogłosili, że nikt nie może być godzien zastąpić takiego króla. W ten sposób monarchia została zniesiona, a w jej miejsce ustanowiono nowy urząd — archonta — tytuł władzy bez korony. Po śmierci ojca Androklos pozostał bez tronu, lecz nie bez celu. Z niespokojnym duchem i królewskim dziedzictwem zebrał towarzyszy i okręty, by wyruszyć przez Morze Egejskie na poszukiwanie nowej ziemi, nowych Aten po drugiej stronie morza.

Zanim wypłynął, jak przystało na bohatera tamtych czasów, udał się do wyroczni w Delfach. Pytia, w jej zagadkowym tonie, wydała przepowiednię: "Ryba i dzik wskażą ci miejsce." Jak wiele delfickich wyroczni, była to zagadka równie tajemnicza, co prorocza — zmuszająca do szukania znaczenia nie w rozumie, lecz w przeznaczeniu.

Niezrażony Androklos poprowadził swój lud wzdłuż wybrzeży Azji Mniejszej, badając żyzne doliny i spokojne zatoki. Pewnego dnia, gdy jego ludzie przygotowywali posiłek na brzegu, ryba wyskoczyła z patelni, rozrzucając żar na pobliskie krzewy. Iskry zapaliły zarośla, a z krzaków wyskoczył spłoszony dzik. Androklos rozpoznał w tym znak boski. Pochwycił włócznię i ruszył w pogoń. Gdy zwierzę padło, wiedział, że to właśnie tu — w miejscu, które wskazał Apollo — powinno powstać jego nowe miasto.

Tak więc na stokach w pobliżu ujścia rzeki Kaystros Androklos założył Efez. Legenda głosi, że wzniósł pierwsze mury i świątynie, być może nawet położył fundamenty pod sanktuarium, które z czasem stało się słynną Świątynią Artemidy — jednym z Siedmiu Cudów Starożytnego Świata. Panował mądrze i odważnie, zasłynął jako znakomity wojownik i władca o wizji jedności. To on zjednoczył dwanaście miast jońskich w Związek Joński, zapewniając im współpracę i wspólną obronę. Pod jego rządami Efez wyrósł z niewielkiej osady w kwitnące nadmorskie polis.

Androklos zginął jako bohater w bitwie, wspierając jońskie miasto Priene przeciw Karyjczykom, którzy często walczyli z osadzającymi się na wybrzeżu Grekami. Pauzaniasz przekazuje, że jego towarzysze zanieśli ciało króla do Efezu i pochowali je w obrębie murów miasta. Na jego grobie, jak pisał, stał posąg uzbrojonego mężczyzny — być może przypomnienie o wojowniku, który kiedyś zapolował na dzika i założył miasto.

Ta wzmianka zainspirowała niektórych badaczy do utożsamienia tzw. Heroonu Androklosa, położonego nieopodal Biblioteki Celsusa w Efezie, z jego grobem. Hellenistyczny monument, wzniesiony w II wieku p.n.e. na zachodnim krańcu Ulicy Kuretów, był heroonem — sanktuarium poświęconym bohaterskiemu przodkowi. Miał kształt litery U, z dorycką fasadą na parterze i otwartym górnym piętrem w porządku jońskim. Przed budowlą znajdował się kamienny zbiornik na wodę, później przekształcony w fontannę, przez co późniejsze pokolenia nazywały budowlę Fontanną Bizantyjską. W późnej starożytności marmurowe płyty obiektu ozdobiono krzyżami, co dodatkowo zaciemniło jego pierwotną funkcję.

Kluczem do jego interpretacji okazał się relief znaleziony wśród ruin. Przedstawia on jeźdźca w krótkim chitonie, z płaszczem powiewającym na wietrze, pędzącego do bitwy. Wokół niego widać hoplitę, woźnicę i nagą postać bohatera poległego w walce. Dla wielu uczonych scena ta symbolizuje śmierć wielkiego założyciela — być może samego Androklosa — czczonego przez mieszkańców Efezu jako wojownik i obrońca. W pobliżu odnaleziono również podstawę z inskrypcją dedykowaną ktistesowi, czyli "założycielowi", co wzmocniło tę romantyczną hipotezę.

A jednak ostrożność powinna iść w parze z wyobraźnią. Utożsamienie heroonu z grobem Androklosa pozostaje niepewne. Budowla nie zawierała komory grobowej, co sugeruje, że mogła być pomnikiem czysto pamiątkowym, a nie miejscem pochówku. Co więcej, dowody archeologiczne wskazują, że najstarsza osada jońska nie znajdowała się między wzgórzami Pion i Koressos, gdzie stoi heroon, lecz bliżej wzgórza Ayasuluk. Jeśli Androklos naprawdę istniał, jego miejsce spoczynku mogło leżeć gdzie indziej — być może ukryte pod warstwami ziemi i ruin, które przez stulecia przykryły początki miasta.