Meanwhile four more legions were en route to Lepidus from Africa in merchant ships, being the remainder of his army. Papias, one of Pompeius' captains, threw himself in their way on the sea, and, after they had received him as a friend (for they thought that these were ships sent by Lepidus to meet them), destroyed them. Some ships were despatched by Lepidus leisurely, and when these were approaching, the merchant ships that had escaped mistook them for other enemies and fled. So some of them were burned, some captured, some upset, and the rest returned to Africa. Two legions perished in the sea, or, if any of them could swim, Tisienus, the lieutenant of Pompeius, slew them when they reached the land.
The other legions re-embarked and joined Lepidus, some sooner and some later. Papias sailed back to Pompeius.Octavian crossed from Vibo with his whole fleet to Strongyle,one of the five Aeolian islands, having made a reconnaissance of the sea beforehand. Seeing large forces in front of him on the Sicilian shore at Pelorum, Mylae, and Tyndaris, he conjectured that Pompeius himself was there. So he left Agrippa in command and returned again to Vibo, and thence hastened with Messala and three legions to the camp of Taurus, intending to seize Tauromenium while Pompeius was still absent, and thus threaten him on two sides at once. In pursuance of this plan Agrippa moved forward from Strongyle to the island of Hiera,
and as Pompeius' garrison made no resistance he occupied it and intended on the following day to attack, at Mylae, Demochares, the lieutenant of Pompeius, who had forty ships. Pompeius observed the menacing attitude of Agrippa and sent to Demochares from Messana forty-five ships, under the command of his freedman Apollophanes, and followed in person with seventy others.Agrippa, with half of his ships, sailed out of Hiera before daylight in order to have a naval engagement with Papias only. When he saw the fleet of Apollophanes also, and seventy ships on the other wing, he sent word to Octavian at once that Pompeius was at Mylae with the greater part of his naval forces.