Dimension hopping Harold Shea, having returned home to his psychological practice, is visited by the malevolent enchanter Malambroso, an enemy of Shea and his partner Reed Chalmers who has also discovered the secret of transdimensional travel. Having been thwarted in his attempt to steal Chalmers' wife Florimel in previous adventures, the enchanter attempts to subvert Shea into aiding him. Rebuffed, he threatens vengeance, which he shortly puts into practice by kidnapping Voglinda, the young daughter of Shea and his wife Belphebe of Faerie.

In their search for their daughter, Harold and Belphebe find Malambroso has been residing in their world for some time, and from reading material discovered in his abandoned dwelling discover that he had become a fan of the Barsoom novels of Edgar Rice Burroughs. Reasoning that it is this alternate vision of Mars to which their foe has fled with the girl, they determine to travel there themselves by means of the symbolic logic formulas originally devised by Chalmers. Accordingly, they outfit themselves for the journey, or rather, de-outfit themselves, much to Belphebe's embarrassment; Burroughs' Barsoomians go about largely naked.

Arriving on Barsoom, the Sheas seek out the aid of the royal family of the city-state of Helium, which includes Burroughs' protagonist, the transplanted earthman John Carter. Carter is not present, but they manage to obtain an audience with his father-in-law, Mors Kajak, "jed" (king) of Lesser Helium. Kajak turns out to be somewhat sour on earthmen, including his own son-in-law, presenting a picture of them very different from that of Burroughs. He regards Carter as something of a blowhard, claiming impossible prowess in battle, and Ulysses Paxton, the other earthman resident on Barsoom, as a rabble-rouser, advocating Terran ideas of equality and freedom unwelcome to the hierarchical, slave-owning Martians.

Kajak suggests they seek guidance from Paxton's old mentor Ras Thavas, the so-called "master-mind of Mars," formerly villainous and still somewhat amoral. Thavas consents to aid the couple in return for some professional help from psychologist Shea; having previously had Paxton transplant his brain from his original aged body into a young and virile one, he has had difficulty adjusting to changed societal expectations, not to mention the youthful urges of his new form. With his assistance it is discovered that Malambroso has sought refuge in the one Barsoomian city-state that has shown itself receptive to Paxton's ideas – Zodanga, the traditional foe of Helium.

Together, the Sheas and Thavas succeed in tracking down Malambroso, first on thoat-back to Zodanga, and then by flier to the Great Toonoolian Marshes, with a stopover in Ptarth when their flier is damaged in an air skirmish. Over the course of their journey, Shea counsels the irascible genius successfully. Barsoom is found to be somewhat divergent from the romantic world written of by Burroughs. While the beasts are generally multi-legged, as described, the number of their limbs tend to be fewer than reported. Aside from in the medical area, the superior technology of the Martians has likewise been exaggerated, more comparable to that of Earth's nineteenth century than the futuristic vision portrayed in the novels. And as for Barsoomian honor, vaunted as much by Thavas as it had been by Carter, they are quickly disillusioned when a Zodangan makes a crude pass at Belphebe. On the other hand, Thavas provides something of a corrective to the jaundiced Kajak's view of Carter, who in his experience is a genuinely charismatic leader who can exact pledges of a defeated foe and make them stick. He attributes his own reform to Carter's influence.

The final battle is between Harold and an assassin hired by the enchanter to do his dirty work; they prove fairly evenly matched swordsmen until Thavas, with his superior mental powers, makes the hired killer believe he is confronting six Harolds rather than one. The assassin then abandons the conflict, and Belphebe shoots Malambroso with her bow. Voglinda is safe, as the villain had grown somewhat fond of and paternal toward his captive while on the lam from the Sheas.

Thavas uses his medical skills to save the life of the enchanter to keep Belphebe out of trouble with the law (a sword duel is considered a fair fight by Barsoomians, while a shooting death is murder). The recovering Malambroso abandons his vendetta; having become smitten by his Barsoomian nurse, he forswears his previous infatuation with Florimel. Satisfied, the Sheas depart, though not (immediately) to their home dimension; their pursuit has been costly, and they need to return their rented flier to Zodanga to recover their deposit on it, and resell the purchased thoats they had left there.

In previous tales Harold indulged his yearning for romantic adventure; this one, as in de Camp's immediately preceding Harold Shea story "Sir Harold and the Gnome King", brings his more practical characteristics to the fore. It continues the changes marked by the earlier work in both the fantasy worlds visited by the protagonist to and the manner in which they are portrayed.

Previous venues were generally based on mythology or pre-modern fantastic literature; these were depicted faithfully according to the original sources, and much of the action involved puzzling out and becoming proficient in the magical systems holding sway in them. Now the venues are drawn from modern fantasy or science fiction and are re-imagined in a way that strips them of what de Camp regards as their more absurd aspects. Thus, exploration of the source material is displaced by a revisionist view of it, while the protagonists’ interest in figuring out the local physics gives way to the pursuit of more immediate goals. In the present tale there isn't even a magical system to explore in the first place.

Unlike "Sir Harold and the Gnome King," in which de Camp's alterations of the original venue are attributable to events in the venue itself and the different viewpoint of the protagonist, the vision of Barsoom articulated in the present story is incompatible with Burroughs' original stories. While de Camp rationalizes his changes by attributing Burroughs's portrayal as erroneous reporting, the method of dimensional travel utilized by his characters depends on that reporting, in that the destination world is set by it. Thus, absurd or not, Malambroso and the Sheas should have ended up in the "erroneous" Burroughs version of Barsoom, not the "correct" de Camp version. Possibly de Camp's implication is that Burroughs' version would be impossible in any universe, and the one his characters reach is the closest approximation.

In any case, the "absurdities" dispensed with in de Camp's version of Barsoom include the impossible swordsmanship of John Carter, the unlikely rectitude and supposedly advanced technology of the inhabitants, the excessive attributes of the fauna (multitudinous limbs, physically impossible size, as of the supposedly gigantic hornet-like siths), and like matters, all set down to the exaggerated storytelling of Carter, Burroughs, or both. It is a firmly de-romanticized Barsoom through which the Sheas travel.

The story shares with its predecessor another inconsistency with previous entries in the series, in that the era in which it takes place seems to have been silently revised from the 1940s of the original tales to the 1990s in which it was written. In the most notable instance, the Burroughs works Malambroso is found to have read consist of contemporary paperback copies in addition to the editions available earlier in the century, and the Sheas too appear familiar with the later versions.