Le neuvième des Travaux d'Héraclès fut d'apporter à la fille d'Eurysthée, Admètè, la ceinture d'or d'Arès, que portait la reine des Amazones, Hippolytè. Ayant frété un navire, et réuni une troupe de volontaires, parmi lesquels se trouvaient Iolaos, Télamon d'Egine, Pelée d'Iolcos et, d'après quelques récits, Thésée d'Athènes, Héraclès mit à la voile en direction du fleuve Thermodon.
Au moment où Héraclès se rendit chez les amazones, elles avaient toutes regagné le fleuve Thermodon et leurs trois villes étaient gouvernées par Hippolytè, Antiope et Mélanippe. En chemin il s'arrêta à l île de Paros, célèbre pour son marbre le roi Rhadamanthe l'avait léguée à un certain Alcée, fils d'Androgée mais quatre des fils de Minos, Eurymédon, Chrysès, Néphalion et Philolaos, s'y étaient également fixés. Après le meurtre de deux membres de l'équipage d'Héraclès descendus à terre pour chercher de l'eau par les fils de Minos, Héraclès indigné les avait tués tous les quatre et avait attaqué si violemment les habitants de Paros que ceux-ci lui avaient envoyé des émissaires pour lui offrir en dédommagement des deux marins tués, deux hommes qu'il choisirait et qui seraient ses esclaves. Satisfait de cette réparation, Héraclès leva le siège et choisit le roi Alcée et son frère Sthénélos qu'il prit à bord de son navire. Ensuite, il voyagea à travers l'Hellespont et sur le Bosphore jusqu'à Mariandyne, en Mysie, où il fut reçu par le roi Lycos de Paphlagonie, fils de Dascylos et petit-fils de Tantale. En échange, il aida Lycos dans une guerre contre les Bébryces, dont il tua un grand nombre, parmi lesquels leur roi Mygdon, frère d'Amycos; il reprit une grande partie du territoire de Paphlagonie aux Bébryces, qu'il rendit à Lycos; celui-ci lui donna le nom d'Héracléide, en l'honneur d'Héraclès. Par la suite Héracléia fut colonisée par les Mégariens et les Tanagriens, sur le conseil de la Pythie de Delphes qui leur recommanda de fonder une colonie près de la mer Noire, dans une région dédiée à Héraclès.
Parvenu à l'embouchure du Thermodon, Héraclès jeta l'ancre dans le port de
Thémiscyra où
Hippolytè lui rendit visite, séduite par son physique et sa belle musculature,
elle lui offrit la ceinture d'Arès en témoignage d'amour.
Mais entre-temps Héra,
déguisée en Amazone, était allée partout répandre le bruit que ces étrangers
avaient l'intention d'enlever Hippolytè; les femmes-guerriers alors,
pleines de courroux, sautèrent en selle et attaquèrent le navire.
Héraclès,
croyant à une trahison, tua Hippolytè de sa main lui retira sa ceinture,
prit sa hache et d'autres armes et se prépara à se défendre.
Il tua tour à tour
toutes les Amazones qui dirigeaient la bataille, et mit en déroute leur armée
après un terrible massacre.
A son retour de Thémiscyra, Héraclès revint à Mariandyne et prit part aux jeux funèbres du frère du roi Lycos, Priolas, qui avait été tué par les Mysiens. Héraclès boxa contre le champion Mariandynien Titias, lui brisa toutes les dents et le tua d'un coup de poing à la tempe. Pour manifester son regret à la suite de cet accident, il soumit les Mysiens et les Phrygiens en faveur de Dascylos; mais il soumit également les Bithyniens jusqu'à l'embouchure du fleuve Rhebas et au sommet du mont Colone et revendiqua leur royaume pour lui-même. Les Paphlagoniens de Pélops se rendirent de leur propre gré. Cependant à peine Héraclès était-il parti que les Bébryces, sous la conduite d'Amycos, fils de Poséidon, s'emparèrent, une fois de plus, du territoire de Lycos, étendant ainsi leurs frontières jusqu'au fleuve Hypios.