Они должны были достигнуть самых дальних берегов Эвксинского Понта, — именно там находилась страна амазонок со столицей Фемискирой. По пути Геракл пристал со своими спутниками к острову Паросу, где правили сыновья Миноса. На этом острове сыновья Миноса убили двух спутников Геракла. Геракл тотчас же начал войну с сыновьями Миноса. Многих жителей Пароса он перебил, других же, загнав в город, держал в осаде до тех пор, пока не послали осажденные послов к Гераклу и не стали просить его, чтобы он взял двоих из них вместо убитых спутников.
С Пароса Геракл прибыл в Мизию к царю Лику, который принял его с великим гостеприимством. На Лика неожиданно напал царь бебриков. Геракл победил со своим отрядом царя бебриков и разрушил его столицу, а всю землю бебриков отдал Лику. И тогда царь Лик назвал эту страну в честь Геракла Гераклеей. После этого подвига Геракл отправился дальше и наконец прибыл к городу амазонок Фемискире.
Слава о подвигах сына Зевса давно уже достигла страны амазонок.
— Славный сын Зевса, скажи мне, что привело тебя в наш город? Мир несешь ты нам или войну? — спросила великого героя Геракла царица Ипполита.
Геракл ответил царице:
— Царица, не по своей воле пришел я сюда с войском, совершив далекий путь по бурному морю; меня прислал властитель Микен Эврисфей.
Ипполита не в силах была ни в чем отказать Гераклу. Она была уже готова добровольно отдать ему пояс, но великая Гера, желая погубить ненавистного ей Геракла, приняла вид амазонки, вмешалась в толпу и стала убеждать воительниц напасть на войско Геракла.
— Неправду говорит Геракл, — сказала Гера амазонкам, — он явился к вам с коварным умыслом: герой хочет похитить вашу царицу Ипполиту и увезти ее рабыней в свой дом.
"Поверили амазонки Гере. Схватились они за оружие и напали на войско Геракла. Впереди войска амазонок неслась быстрая, как ветер, Аэлла. Она, подобно бурному вихрю, первой напала на Геракла. Великий герой отразил ее натиск и обратил ее в бегство. Аэлла думала спастись, но не помогла ей вся ее прыть. Геракл настиг ее и поразил своим сверкающим мечом. Погибла в сраженье и Протоя.