As a result of a second Maunder Minimum, economic power in the First System has shifted to the moons around Jupiter. The Europan Demarchy controls Europa and Io; Gilgamesh Isis controls Ganymede and Callisto. Both powers are vying for dominance. Marius Vargovic is a Gilgamesh agent who has been deployed to Europa to meet a woman known as Cholok, who has something that could threaten the cities of Europa. He lands in the city of Cadmus-Asterius, or C-A, a floating city whose top is built into the ice, but which descends eight kilometres into the ocean below. They meet in the city and Cholok reveals that she has a piece of "Hyperdiamond", a carbon compound that is extremely strong – individual molecules can be hundreds of metres in diameter. Floating spheres of vacuum encased in hyperdiamond keep the city from sinking. If Gilgamesh can find a way to tamper with it, they could cause the Europan cities to collapse.
Marius is then operated on to give him the ability to breathe underwater. He asks Cholok about "Denizens", experimental cross-breeds between humans and fish to create the perfect underwater worker. She denies their existence. Marius kills her and leaves the city. As he swims northward to his extraction point, he is informed that it has been compromised. He swims southward, but the Demarchy is trailing him. He meets a group of Denizens who kill the Demarchist agents and inform him that Cholok created them, but the Demarchy turned them away and imprisoned them in their cave. The cave was warm enough to survive in, but if they went outside, their blood would freeze. Normally, they could make "glycoproteins" that would lower their freezing temperature, but the Demarchy has deactivated them. Cholok has, however, inserted a virus into Marius's blood that will reactivate the genes to make the proteins. To get it, they need to drink his blood. As such, they kill him.
A Spy in Europa was first published in an issue of British science fiction magazine Interzone, specifically Interzone 120 in June 1997.