The story consists of alternating sections set on Earth and in Zimiamvia. The Earth sections focus on the romance of Edward Lessingham and his wife Mary. The Zimiamvian sections describe King Mezentius, described as "tyrant of Fingiswold, Meszria and Rerek", foiling a plot against his Vicar in Rerek, and then the romance of his illegitimate son Barganax with the Lady Fiorinda. The fish dinner of the title turns into a symposium on Eddison's metaphysics.
Much is revealed about the links between principal characters and the separate worlds of the novel, as well as to The Worm Ouroboros, not fully resolved in the other novels in the trilogy. The character of Lessingham is also resolved to its greatest extent in all the novels of the trilogy.
A Fish Dinner in Memison overlaps chronologically with The Mezentian Gate, but since the action starts later than in that work, it can be considered chronologically as the second novel in the series.