The siege was conducted by the Roman proconsul Marcus Aurelius Cotta (by land) and the legate Gaius Valerius Triarius (by sea).

Heraclea was located on the strategically important northern land route into the kingdom of Pontus and had been taken and garrisoned by Mithridates on his retreat from the Siege of Cyzicus.

[3] Bithynia served as a buffer state between Rome and Pontus; feeling threatened Mithridates marched his armies westwards and invade Roman territory.

Lucullus had not advanced far when news came through that Mithridates had made a rapid march westward, attacked and defeated Cotta at the Battle of Chalcedon, and was now besieging him.

[8] Menchares, one of the sons of Mithridates and his governor of the Bosporian Kingdom, supplied Heraclea and its defenders from his dominions north of the Black Sea.

The plan was apparently common knowledge in Heraclea –Connacorex had deceived the Heracleans by telling them he had received word that Mithridates and Tigranes (his ally) were on their way and would soon drive the Romans out.

Triarius went in pursuit of Connacorex, who had captured Tius and Amastris; he was eventually allowed to flee, with the Romans taking the cities without a fight.