Mentor's career as mercenary leader started when he was twenty-seven years old. In 358, he served under an important Persian nobleman, Artabazus, the satrap of Hellespontine Phrygia, a province of the Achaemenid empire in the northwest of modern Turkey. For reasons that are not completely clear to us, Artabazus stood up against the new Persian king Artaxerxes III Ochus. Mentor and his brother Memnon were to lead his army. To conclude the alliance, the rebel satrap married their sister and Mentor married his daughter Barsine. Their marriage was not consumed yet, because Barsine was too young. The two brothers also received land near ancient Troy.
Although Mentor and Memnon were capable commanders and received help from a Greek contingent from Thebes, they were unable to repel the Persian army that Artaxerxes sent in the first months of 354. Artabazus, Barsine and Memnon fled to Pella, the capital of Macedonia, where king Philip (360-336) welcomed them and invited them to stay as long as they liked.
Mentor fled to Egypt, which was at that time independent. Pharaoh Nakhthorhebe or Nectanebo II (360-343), who expected a Persian invasion, was glad to receive an experienced mercenary commander who knew the Persian way of war.
Mentor was immediately sent to the Phoenician town Sidon (c.350). He commanded 4,000 Greek mercenaries and was to support king Tennes (Phoenician Tabnit), who had revolted from his Persian overlord. Tennes and Mentor defeated the satraps Mazaeus and Belysis of Cilicia and Syria, but knew that they did not stand a chance against the army of Artaxerxes himself. When it appeared in 346 - earlier dates are less likely - Tennes and Mentor betrayed the city. Nonetheless, Tennes was killed by the Persians and the desperate Sidonians set fire to their own city.
The great king pardoned Mentor, who was to serve in the royal army. In November 343, Artaxerxes attacked and reoccupied Egypt and Mentor offered invaluable services. By now, he knew how to get things done at the Persian court. He aligned himself with the influential eunuch Bagoas, who had also played an important role in the reconquest of Egypt. Together, they managed to convince the king that they were of invaluable service to the Achaemenid empire, and they were rewarded with important new commands: Bagoas in the eastern satrapies, Mentor in the west, where he arrived in 342.
Artaxerxes also allowed his new supreme commander in the west to pardon his father-in-law Artabazus, who had been living in Macedonia for twelve years. The former exile offered the king invaluable information about the plan of king Philip to attack Persia, which was to be executed as soon as he had subdued the Greek cities. (It was in fact executed by Philip's son Alexander the Great.)
Mentor did not long enjoy his new position. His only known action was directed against Hermias, the tyrant of the Greek cities Atarneus and Assus. (He was the host of the famous Macedonian philosopher Aristotle of Stagira, whom he married to his cousin Pythias.) Hermias had made no secret of his sympathy for the Macedonian cause, and Mentor had him arrested. This is his last known action, but he may somehow been involved in the overthrow of the satrap of Caria, Ada, by her brother Pixodarus. The Persian supreme commander in the west died in 340.
Mentor and Barsine had a daughter, who married Nearchus, the fleet commander of Alexander the Great (324). Barsine remarried to Memnon; after his death, she became the mistress of Alexander.