Although they are not formally married, the most important romantic relationship that Hermes has is with the Goddess Aphrodite, with whom he shared a temple at Olbia on the Black Sea. We have records of a magical duel conducted by Pharnabazos, a diviner of Hermes who worked out of this temple, and one of his rivals; it is also possible that Pharnabazos was the Orpheotelest who inscribed enigmatic signs and phrases on the bone tablets found nearby. (For more on this matter consult Andrei V . Lebedev’s Pharnabazos the diviner of Hermes and The Devotio of Xanthippus: Magic and Mystery Cults in Olbia.) 

We find a similar pairing in the Magna Graecian city of Lokroi Epizephyrii where their temple contained a series of pinakes or terracotta plates: 

On two pinax types they appear together as cult statues. In one example Aphrodite stands facing Hermes, extending the offering of what appears to be a lotus blossom. Eros stands on her outstretched right forearm, mimicking her gesture with his own extended right arm; he holds a tortoise shell lyre in his left hand. Hermes holds the kerkyreion in his right hand and there is a thymiaterion between the divine pair. The scene appears to represent a meeting between the two divine lovers but we have no mythological context in which to place the scene. […] On the next example Aphrodite and Hermes are clearly shown as cult statues inside a temple of mixed Ionic and Doric orders. The statue of Hermes is nude except for a chlamys draped over his shoulders and his petasos, travelling hat. He holds a patera in his right hand. Aphrodite is clothed in a peplos and her hair is worn down with a filet at the top. She appears to be holding a dove in her right hand but most of the remaining examples are badly damaged at this point. In front of the temple, a bare-foot young woman and young man are pouring a libation on an altar. The plaque is iconographically rich and suggestive of Aphrodite and Hermes’ cultic “personality” at Locri. The seemingly somber libation being performed by the mortal couple is subtly undermined by the erotic relief on the altar — a satyr copulating with a hind. This complicates the interpretation of the plaque. In the overall context of the pinakes the mortal couple would seem to be either betrothed or married. However, they are pouring a libation to an unwed divine couple on an altar. depicting an erotic sexual act that stands outside the bounds of the civic intercourse necessary for reproduction. I would argue, therefore, that this pinax type would have been a dedication made by worshippers of Aphrodite who fall outside the bounds of ‘civic society’ but who also recognize the overall power of the Mannella sanctuary to protect all women within Locrian society. (Rebecca K. Schindler, Aphrodite and the Colonization of Lokroi Epizephyri) 

The concern of Hermes and Aphrodite for individuals and couples who do not conform to societal norms is perhaps most potently expressed through their child Hermaphroditos:

… whose name is a combination of his parents’ names. Some say that this Hermaphroditos is a God and appears at certain times among men, and that he is born with a physical body which is a combination of male and female elements, in that he has a body which is beautiful and delicate like that of a woman, but also possesses male genitalia and the vigour of a man. There are some however who declare that such two-sexed creatures are monstrosities, and coming rarely into the world as they do they have the quality of presaging the future, sometimes for evil and sometimes for good. (Diodoros Sikeliotes, Library of History 4.6.5)

Hermaphroditos was the prototype for the Enarees, a group of gender-variant diviners described by Herodotos:

But the Skythians who pillaged the temple, and all their descendants after them, were afflicted by the Goddess with the “female sickness”: and so it is that visitors to the Skythian territory see among them many who are in the condition of what the Skythians call Hermaphrodites. (Histories 1.105.4)

There are many diviners among the Skythians who divine by means of willow wands. They bring great bundles of wands, which they lay on the ground and unfasten, and utter their divinations as they lay the rods down one by one; and while still speaking, they gather up the rods once more and place them together again; this manner of divination is hereditary among them. The Enarees, who are Hermaphrodites, say that Aphrodite gave them another art of divination, which they practise by means of lime-tree bark. They cut this bark into three portions, and prophesy while they braid and unbraid these in their fingers. (ibid 4.67.1)

Aphrodite is not Hermes’ only romantic partner, however. 

There is his union with the Witch-Goddess Hekate from the Black Sea region: 

We are told that Helios had two sons, Aeëtes and Perses, Aeëtes being the king of Kolchis and the other king of the Tauric Chersonese, and that both of them were exceedingly cruel. And Perses had a daughter Hekate, who surpassed her father in boldness and lawlessness. she was also fond of hunting, and when she had no luck she would turn her arrows upon human beings instead of the beasts. Being likewise ingenious in the mixing of deadly poisons she discovered the drug called aconite and tried out the strength of each poison by mixing it with food given to strangers. 

Which also resulted in the production of an androgynous child, Hermekate:

I call upon you, Mother of all men,
you who have brought together the limbs of Meliouchos,
even Meliouchos himself,
OROBASTRIA NEBOUTOSOUALETH
Entrapper, Mistress of Corpses,
Hermes, Hekate, Hermekate
LETH AMOUMAMOUTERMYOR
I conjure you, the daimon that has been aroused in this place,
and you, the daimon of the cat that has been endowed with spirit.
Come to me this very day and from this very moment,
and perform for me the NN deed…
(PGM III 45-52)

He lay with the mysterious Brimo:

Brimo, who as legend tells, by the waters of Boebeis laid her virgin body at Mercury’s side. (Propertius, Elegies 2.29)

And also Chione (whose name means “Snowy”) by whom he had Autolykos, the shapeshifting trickster and thief (whose name means “the wolf itself”) who was responsible for naming his world-famous grandson:

Autolykos was the noble father of Odysseus’ own mother, and excelled all mankind in thieving and subtlety of oaths, having won this mastery from the God Hermes himself, for to him he was wont to burn acceptable sacrifices of the thighs of lambs and kids; so Hermes befriended him with a ready heart. Now Autolykos, on coming once to the rich land of Ithaka, had found his daughter’s son a babe new-born, and when he was finishing his supper, Eurykleia laid the child upon his knees and spoke, addressing him: “Autolykos, find now thyself a name to give to thy child’s own child; be sure he has long been prayed for.” Then Autolykos answered: “Since I have been angered (ὀδυσσάμενος; odyssamenos) with many, both men and women, let the name of the child be Odysseus.” (Homer, Odyssey 19.395-410)

Hermes blessed and watched over clever Odysseus, even when he wandered among Northern barbarians:

Moreover, some speculate that Ulysses, driven on that long and fantastic journey to this Ocean, had himself come to the lands of Germany, and that Asciburgium, which was located on the bank of the Rhine and is inhabited even today, was founded and named by him. Nay, even more, they say that there was found in that same place an altar consecrated to Ulysses, which bears also the name of his father Laeertes; further, there are monuments and tombs bearing inscriptions in Greek letters which are still extant today on the borders of Germany and Raetia. I have no intention either of confirming or refuting these speculations: everyone may either add or withdraw his belief according to the inclination of his own mind. (Tacitus, Germania 3)

When Odysseus encountered Kírkē (herself an émigré from the Black Sea) Hermes was there to offer counsel and the magical plant μῶλυ (moly) which rendered the hero immune to the Goddess’ sensual sorcery. 

Her response to Odysseus’ challenge suggests that Kírkē was on rather familiar terms with Hermes:

“Who are you, and from where? Where are your city and your parents? It bewilders me that you drank this drug and were not bewitched. Never has any other man resisted this drug, once he had drunk it and let it pass his lips. But you have an inner will that is proof against sorcery. You must surely be that man of wide-ranging spirit, Odysseus himself; the Radiant One of the golden wand has told me of you; he always said that Odysseus would come to me on his way from Troy in his dark and rapid vessel.” (Homer, Odyssey 10)

This dalliance has added significance within the Starry Bear tradition, for we understand Kírkē to be one of the personae adopted by Freyja as she searched for her lost husband Ódr, whom we identify with Dionysos:

Freyja is most gently born (together with Frigg): she is wedded to the man named Ódr. Their daughter is Hnoss: she is so fair, that those things which are fair and precious are called hnossir. Ódr went away on long journeys, and Freyja weeps for him, and her tears are red gold. Freyja has many names, and this is the cause thereof: that she gave herself sundry names when she went out among unknown peoples seeking Ódr: she is called Mardöll and Hörn, Gefn, Sýr. Freyja had the necklace Brísinga-men. She is also called Lady of the Vanir. (Gylfaginning 29)

Odysseus we likewise regard as Ódr, having forgotten his true identity – which gives added poignancy to the question Kírkē puts to him. (As does the one-eyed Polyphemos, whom he answers – Οὖτις; “Nobody.”) 

Accepting this, however, means that on some level Hermes is the progenitor of Dionysos, or at least one of the mortal lines that he incarnated into. This is no stranger, however, than what we find in the cult-hymn of a group of Orphics from Asia Minor:

Orphic Hymn 57. To Chthonic Hermes
Incense: Storax
You dwell in the compelling road of no return, by the Kytos.
You guide the souls of mortals to the nether gloom.
Hermes, offspring of Dionysos who revels in dance,
and Aphrodite, the Paphian maiden of the fluttering eyelids,
you who frequent the sacred house of Persephone,
as guide throughout the earth of ill-fated souls,
which you bring to their haven when their time has come,
charming them with your sacred wand and giving them sleep,
from which you rouse them again.
To you indeed Persephone gave the office 
throughout wide Tartaros to lead the way 
for the eternal souls of men. But, O Blessed One, 
grant a good end for the initiate’s work.

For those familiar with the Battle of the Bull and Wolf mytheme the grandfather of “Odysseus” becomes a very intriguing figure. 

Autolykos – “the wolf itself” – was both a protector of flocks and a devourer of them, and this latter habit had tragic consequences. 

Back when Herakles was a boukolos or cowherder:

Herakles was taught to drive a chariot by Amphitryon, to wrestle by Autolykos, to shoot with the bow by Eurytus, to fence by Kastor, and to play the lyre by Linos. This Linos was a brother of Orpheus; he came to Thebes and became a Theban, but was killed by Herakles with a blow of the lyre; for being struck by him, Herakles flew into a rage and slew him. When he was tried for murder, Herakles quoted a law of Rhadamanthys, who laid it down that whoever defends himself against a wrongful aggressor shall go free, and so he was acquitted. But fearing he might do the like again, Amphitryon sent him to the cattle farm; and there he was nurtured and outdid all in stature and strength. Even by the look of him it was plain that he was a son of Zeus; for his body measured four cubits, and he flashed a gleam of fire from his eyes; and he did not miss, neither with the bow nor with the javelin. While he was with the herds and had reached his eighteenth year he slew the lion of Cithaeron, for that animal, sallying from Cithaeron, harried the kine of Amphitryon and of Thespius. (Apollodoros, The Library 2.4.9)

Autolykos was preying upon his neighbors, for which Herakles was blamed, driving the son of Zeus into another murderous frenzy:

Not long after, some cattle were stolen from Euboea by Autolykos, and Eurytus supposed that it was done by Herakles; but Iphitos did not believe it and went to Herakles. And meeting him, as he came from Pherae after saving the dead Alkestis for Admetos, he invited him to seek the kine with him. Herakles promised to do so and entertained him; but going mad again he threw him from the walls of Tiryns. Wishing to be purified of the murder he repaired to Neleus, who was prince of the Pylians. And when Neleus rejected his request on the score of his friendship with Eurytus, he went to Amyclae and was purified by Deiphobos, son of Hippolytos. But being afflicted with a dire disease on account of the murder of Iphitos he went to Delphi and inquired how he might be rid of the disease. As the Pythian priestess answered him not by oracles, he was fain to plunder the temple, and, carrying off the tripod, to institute an oracle of his own. But Apollon fought him, and Zeus threw a thunderbolt between them. When they had thus been parted, Herakles received an oracle, which declared that the remedy for his disease was for him to be sold, and to serve for three years, and to pay compensation for the murder to Eurytus. (ibid 2.6.2)

Hermes stepped in to help his brother fulfil the oracle and attain healing and release:

After the delivery of the oracle, Hermes sold Herakles, and he was bought by Omphale, daughter of Iardanes, queen of Lydia, to whom at his death her husband Tmolus had bequeathed the government. Eurytus did not accept the compensation when it was presented to him, but Herakles served Omphale as a slave, and in the course of his servitude he seized and bound the Cercopes at Ephesos; and as for Syleus in Aulis, who compelled passing strangers to dig, Herakles killed him with his daughter Xenodoce, after burning the vines with the roots. And having put in to the island of Doliche, he saw the body of Icarus washed ashore and buried it, and he called the island Icaria instead of Doliche. In return Daedalus made a portrait statue of Herakles at Pisa, which Herakles mistook at night for living and threw a stone and hit it. And during the time of his servitude with Omphale it is said that the voyage to Kolchis and the hunt of the Calydonian boar took place, and that Theseus on his way from Troezen cleared the Isthmus of malefactors. (ibid 2.6.3)

During this period of transvestite sexual slavery Omphale instructed Herakles in the mysteries of weaving, much as Óðinn had to submit to Freyja to learn the art of seiðr. 

One wonders if Hermes knew (and perhaps had a prior relationship with) the Lydian Queen Omphale. After all, when Saint Paul was traveling through the region people mistook him for Hermes:

And when the crowds saw what Paul had done, they lifted up their voices, saying in Lycaonian, ‘The Gods have come down to us in the likeness of men!’ Barnabas they called Zeus, and Paul, Hermes, because he was the chief speaker. (Acts 14.11-12)

This is where things get really interesting. For you see, Lycaonia is “wolf country” (from the word lykos) and Hermes has some strong connections with the animal. As a pastoral deity he was invoked to protect the flocks against wolves (just as he was said to have power over guard-dogs in more domestic contexts) and in Hellenistic Egypt he was frequently equated with both Wepwawet and Anubis, to the point where he was depicted with canine features as Hermanubis. Diodoros Sikeliotes mentions these two as a pair of heralds (and Hermes is the God of heraldry) who marched in the army of Osiris-Dionysos:

Now he was accompanied on his campaign, as the Egyptian account goes, by his two sons Anubis and Makedon, who were distinguished for their valour. Both of them carried the most notable accoutrements of war, taken from certain animals whose character was not unlike the boldness of the men, Anubis wearing a dog’s skin and Makedon the foreparts of a wolf; and it is for this reason that these animals are held in honour among the Egyptians … Makedon his son, moreover, he left as king of Makedonia, which was named after him. (1.18ff)

A feature that is curiously paralleled much later on in Nonnos of Panopolis’ epic on the Indian conquest of Dionysos when he speaks of the Satyroi Hermeides:

With Pherespondos walked Lykos the loudvoiced herald, and Pronomos renowned for intelligence – all sons of Hermes, when he had joined Iphthime to himself in secret union. To these three Eiraphiotes entrusted the dignity of the staff of the heavenly herald, their father the source of wisdom. (Dionysiaka 14.105ff)