The colonists soon subjugated the native Mariandynians but agreed to terms that none of the latter, now helot-like serfs, be sold into slavery outside their homeland. Prospering from the rich, fertile adjacent lands and the sea-fisheries of its natural harbor, Heraclea soon extended its control along the coast as far east as Cytorus (Gideros, near Cide), eventually establishing Black Sea colonies of its own (Cytorus, Callatis and Chersonesus).
The Greek historical author Memnon of Heraclea (fl. 1st century AD) wrote a local history of Heraclea Pontica in at least sixteen books. The work has perished, but Photius's Bibliotheca preserves a compressed account of books 9–16, seemingly the only ones extant in his day. These books run from the rule of the tyrant Clearchus (c. 364–353 BC) to the later years of Julius Caesar (c. 40 BC) and contain many colorful accounts including the Bithynian introduction of the barbarian Gauls into Asia where they first allied themselves with the Heracleans and later turned violently against them.