Later in 255 BCE the Romans sent a fleet of 350 quinqueremes and more than 300 transports to evacuate their survivors, who were under siege in Aspis. Both consuls for the year, Servius Fulvius Paetinus Nobilior and Marcus Aemilius Paullus, accompanied the fleet. They captured the island of Cossyra en route.

The Carthaginians attempted to oppose the evacuation with 200 quinqueremes. They intercepted the Romans off Cape Hermaeum (the modern Cape Bon or Ras ed-Dar), a little to the north of Aspis. The 40 Roman ships which had been left to support Regulus's force over the winter sortied from Aspis to join the fight. Few details of the battle have survived. The Carthaginians were concerned they would be encircled by the larger Roman fleet and so sailed close to the coast. However, the Carthaginian ships were outmanoeuvred and pinned against the coast, where many were boarded via the corvus and captured, or forced to beach. The Carthaginians were defeated and 114 of their ships were captured, together with their crews, and 16 sunk. What, if any, the Roman losses were is not known; most modern historians assume there were none. The historian Marc DeSantis suggests that a lack of soldiers serving as marines on the Carthaginian ships, compared with the Romans', may have been a factor in their defeat and in the large number of vessels captured.