NPR.org has a piece with Adrian Goldsworthy, who recently published his latest book Antony and Cleopatra, in which he relates the following fish story:

From Plutarch's "life of Antony"

One instance will suffice. He was fishing once, and had bad luck, and was vexed at it because Cleopatra was there to see. He therefore ordered his fishermen to dive down and secretly fasten to his hook some fish that had been previously caught, and pulled up two or three of them. But the Egyptian saw through the trick, and pretending to admire her lover's skill, told her friends about it, and invited them to be spectators of it the following day.  So great numbers of them got into the fishing boats, and when Antony had let down his line, she ordered one of her own attendants to get the start of him by swimming onto his hook and fastening on it a salted Pontic (which is to say, from the Black Sea) herring. Antony thought he had caught something, and pulled it up, whereupon there was great laughter, as was natural, and Cleopatra said: "Imperator, hand over thy fishing-rod to the fishermen of Pharos and Canopus; thy sport is the hunting of cities, realms, and continents."