The Trojan War that we read about in The Iliad and The 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.
Although the Greek gods could inflict horrible punishments on the general populace, they were unable to get what they were promised from King Laomedon, a man whose salient trait was treachery. Hercules, facing the same broken promise, got more direct revenge by destroying Laomedon's city of Troy (Ilium). These events happened before the destruction of Troy in the Homeric epics, the Iliad and Odyssey.In Apollodorus' stories of Hercules, the Greek hero landed at Troy, after an encounter with the Amazons that resulted in his obtaining Queen Hippolyte's belt. Elsewhere, the Amazon adventure was later. Troy was, at the time, ruled by the father of King Priam of Trojan War fame. This king's name was Laomedon. He was an uncle of Anchises, father of the Trojan prince Aeneas who led his band of followers to Italy and eventually to found Rome. Laomedon's father was Ilus who built the city of Ilium (Troy). Going back another generation, the father of Ilus was Tros, after whom the country of Troy was named. One of Laomedon's uncles was the very Ganymede whom Zeus abducted. In exchange for Ganymede, Zeus gave Tros special horses which Laomedon inherited.
Cities of the period were fortified with walls to prevent the enemy from attacking. Ilium needed a wall. When Apollo and Poseidon presented themselves to Laomedon offering to build him the necessary walls [Iliad 7.452-3*] (either to serve as punishment for rebelling against Zeus or as a plot to test Laomedon), Laomedon took them up on it and promised to pay them specific wages. However, once the walls were built, Laomedon reneged on his promise.
The two gods were unhappy. According to Apollodorus, Apollo sent a pestilence; Poseidon, a sea monster as punishment. To save his city, Laomedon was prepared to expose his daughter Hesione -- as was done in different stories, to Andromeda and Psyche. Hercules arrived in time to prevent Hesione from being eaten by the sea monster. Laomedon promised him his special horses if only he would rescue the princess. Hercules agreed.
Carrying a sword, Hercules approached the enormous sea monster. He allowed himself to be swallowed and spent three days in the monster's interior. He used the sword to sever the sea creature's tongue and then re-emerged -- possibly bald. Hercules asked for his horses, but Laomedon once again reneged.
Hercules couldn't conjure up a sea monster or a plague at will, but what he could do, he did. He called up a band of friends to help him get revenge. The small army -- filling only 6 ships -- sacked Troy and put Laomedon and most of his children to death. Hesione was saved (concubine to Hercules' follower Telamon, the father of Ajax and the first to enter the walled city of Troy), and so was one of her brothers, Podarkes, ransomed with a gold-embroidered veil or redeemed for words against his father. Henceforth Podarkes was known by a new name said to refer etymologically to ransom: His new name was Priam.
Sources:
The Heroes of the Greeks, by C. Kerenyi
Apollodorus
"The Building of the City Walls: Troy and Asgard," by Joseph Fontenrose. The Journal of American Folklore, Vol. 96, No. 379 (Jan. - Mar., 1983), pp. 53-63.
"The Capture of Troy by Heracles," by J. M. Scammell, The Classical Journal, Vol. 29, No. 6 (Mar., 1934) pp. 418-428.
Some ancient writers on the story of Hercules and Hesione:
Pindar, Homer, Ovid, Apollodorus, Sophocles, Euripides, Valerius Flaccus, and Diodorus Siculus
* Iliad 21. 441-57 puts Poseidon on the wall detail with Apollo herding for Laomedon.
