The Trojan War that we read about in the Iliad and Odyssey wasn't the first Trojan War. Hercules, with much less fanfare than Agamemnon, gathered together enough men to fill 6 ships, sailed to Troy, sacked the city and destroyed most of the royal family. One of Hercules' band, Telamon, was father to one of the two Ajaxes who fought in the later, Homeric War. One of the two royal survivors -- children of the king who had so annoyed Hercules that he attacked the king's city for revenge -- was Podarkes, but we know of him as King Priam, father of Paris and Hector.
Read more about why Hercules fought at Troy: Hercules, Hesione, and Laomedon.