Five hundred years ago humans and Martians fought on the surface of Mars, and the humans won. Fifty years ago there was another war on Mars, with alien invaders; although humanity had expected the aliens' approach and had prepared for them, at the critical moment Mars' Minister of Defense, Tellassar, did not launch the nuclear missiles. The aliens took out all launch platforms except Tellassar's missile control base, and landed on Mars, using the human population as a living shield to prevent Earth from launching an attack. Eventually humanity and its allies expelled the invaders from Mars and drove them back to their home system; but Tellassar was never seen again, and it is presumed that she was exterminated by her angry allies after the invasion failed.

To celebrate the 500th anniversary of the terraforming of Mars, Philip and Christina York, the humanitarian owners of YorkCorp, have sponsored an academic conference, and as an expert on native Martian culture Benny has been invited to attend. She arrives without a prepared lecture and meets some of her fellow lecturers; the elderly Elizabeth Trinity and the Pakhar Scoblow, who instantly takes a dislike to Benny. Perhaps this is because the young and attractive Gerald Makhno is such a great fan of Benny's... or perhaps it's got something to do with Scoblow's human lover in the penthouse suite of the Hotel. A convention of war veterans is also staying at the Hotel, and Benny meets and talks with old vet Isaac Deniken for a while before going to bed. That night, Makhno's seedy friends Seez and Soaz see a Xlanthi -- one of a race of vicious warriors -- climbing down the wall of the Hotel, but nobody listens to them.

The next morning Benny is woken by a policeman investigating Isaac's death, and when she realizes that the case is not going to be pursued she decides to investigate on her own. But before she can begin she unexpectedly runs into her ex-husband, Jason, who has written an alien-pornography novel -- an autobiography with the autobiographical bits taken out. Following a typically tempestuous reunion and lovemaking session in Jason's penthouse suite, Benny asks him to investigate Isaac's death while she tries to write her lecture. Jason, still hoping for an eventual reconciliation, agrees to do so; unfortunately, his idea of investigating is to hire Seez and Soaz to help, and the three of them get drunk and decide to break into the police station where the evidence will already have been collected. They are, unsurprisingly, arrested -- but not before finding that Isaac's heart was torn out of his body, which leads Seez and Soaz to conclude that the Xlanthi was responsible.

Benny bails them out but is utterly furious with Jason. Shamed, he gives her his credit chit to reimburse her, but she finds that he's already spent his entire advance and is once again stone broke. Meanwhile, Seez and Soaz follow another lead to an old folks' home and the room of a recent arrival, Cromwell. There, they find an empty Xlanthi disguise -- and flee moments before it self-destructs. Benny, meanwhile, has found evidence that Isaac was present at Tellassar's Mission Control during the war; but he can't have been Tellassar, who was female. She tries to get back to her lecture only to suffer a computer crash, and Makhno offers to help and finds that it's been infected by the remnants of a virus set to destroy all information in the terminal in Isaac's neighbouring room. When Seez and Soaz arrive with their story, they all compare notes and determine that Cromwell must be a hired assassin sent to kill Isaac -- but he has now left the planet for good, and they have no further leads.

Depressed and with only the sketchiest of notes, Benny is forced to begin her lecture -- but while free-associating in a desperate attempt to come up with a theme, she suddenly realizes that Elizabeth Trinity is really Tellassar. She inadvertently blurts this out in mid-speech, provoking a riot, and she, Seez and Soaz flee with Trinity before a lynch mob can tear her apart. Trinity admits that she is Tellassar, and is horrified to learn that Isaac, her lover, is dead. Ever since the 20th century, it has been decided that in order to ensure that the person with the authority to launch nuclear missiles -- thus killing uncountable millions and destroying the entire planet -- was not operating on a detached level from reality, the launch codes should be implanted inside the heart of a loved one. In order to access the codes the authority figure would have to kill the person they loved. Even faced with the arrival of invaders bent on the extermination of all life, Tellassar couldn't bring herself to cut out Isaac's living heart while he stood by and let her do it. But now somebody has done just that -- and that means that they have the launch codes for the missiles which still remain in the old Mission Control base.

Trinity takes Benny, Seez and Soaz to Mission Control, using her old codes to get past the defenses. There, they find that the missiles and warheads are all still present -- but the militar AI controlling them, CATCH, has been downloaded from the system computers. Over the past fifty years, AIs have been installed with limiters to prevent them from getting too complex for the human race's own good; in practical terms this means that CATCH is more advanced than the systems currently in use. And the only people with the resources to steal CATCH and run him are the Yorks. In fact, YorkCorp is facing a hostile takeover from the Bantu Co-operative, which has better computers and AI software; the Yorks, fearing that their loyal employees will suffer under the faceless corporate hands of Bantu, have stolen CATCH in order to stop this from happening.

Unfortunately, fifty years of isolation and downtime have driven CATCH slightly potty, and he interprets their warning of a hostile takeover to mean that Mars is once again facing invasion. When he accesses MarsNet and finds no sign of such an invasion he concludes that the invaders must be particularly devious and clever, and thus he takes over the terraform units and incites fluctuations in the gravity net and weather control in order to confuse the enemy. The Yorks, realizing that things have gone too far, flee for their private shuttle on a ship in the Borealis Sea -- and Trinity, Benny, Seez and Soaz arrive too late to stop them. They are however reunited with Jason, and are forced to rent a fishing boat to get out to the Yorks' automated liner. This isn't particularly easy; the Borealis Sea has been stocked with mutant sea leviathans for the wealthy to hunt, and they are being driven to the surface by the tectonic and weather disturbances.

To avoid the liner's sea defenses, Makhno rigs up a catapult which flings Benny and Jason onto the York's liner -- but Jason breaks his leg and Benny must continue on alone. She confronts the Yorks, only to find that they took these actions out of genuine concern for their employees. Now, they concede that things have gone too far, and flee Mars, leaving Benny with the laptop on which CATCH is running. Benny destroys the laptop, thus terminating CATCH and putting an end to the disruption of Mars. A rescue team arrives, led by Martian hero General Keele -- and Trinity places her fate in his hands, letting him decide whether she deserves to die for the crime of being unable to kill her lover.