A woman named Zan wakes in a medical ward with no memory of who she is or why she's there. She learns in short order that she is in the Legion, a massive system of Organic Technology world-ships; that the aforementioned Legion is slowly dying and massive wars are being waged for control of it; and that this is only the latest of many times that she has returned sans memory from a mission to take control of the Mokshi, an errant world-ship believed to be the key to the Legion's salvation.
It's obvious that the people around Zan aren't telling her everything, though, and before long she stumbles into a deadly web of plots and intrigue—some of which she laid herself.
The Stars Are Legion contains examples of the following tropes:
- Ambiguously Human: The inhabitants of the Legion are certainly humanoid, and have at least some human anatomy such as wombs, but their actual origin is never revealed (and given the state of the Legion, may well be lost to history).
- Amnesiac Dissonance: The more Zan runs into traces of her past self, the more she feels that she wouldn't like the person that she used to be. In the end, she chooses not to reclaim her lost memories and instead embraces the person she currently is.
- Amnesiac Resonance: Zan finds herself instinctively knowing the sign language used to communicate in space battles, and old sayings come out of her mouth without any memory of where she learned them.
- Chekhov's Gun: One of the first things Zan notes about herself early in the book is that her left hand is smaller and more deformed than her right. As Lord Mokshi, she was the original owner of the metal arm, and like its other wearers she had to mutilate her flesh arm in order to wear it. When she reclaims it in the climax, it fits like a glove.
- Contemplate Our Navels: Every chapter has an Epigraph from Lord Mokshi AKA Zan, containing philosophical musings that are usually relevant to the events of that chapter.
- Human Resources: The point of "recycling," where dead, defective, or unwanted individuals are dumped into the world's core to be digested and reused.
- I Am Who?: Naturally, Zan's former identity is a Driving Question of the novel, with the people around her giving anything from incomplete answers to outright lies. It turns out Zan is Lord Mokshi herself, which is why she's the only person who can pierce the world-ship's defenses.
- I Did What I Had to Do: Jayd's attitude towards all the horrible things she's done in service to the plan she and Zan came up with. Lord Mokshi's epigraphs show some of this as well.
- The Ghost: Lord Mokshi has a quote at the head of every chapter but is conspicuously absent from the main story even as it revolves around the Mokshi itself. When we finally find out that she is Zan—or rather, that Zan was her—the Amnesiac Dissonance makes her more of a Posthumous Character.
- God Save Us from the Queen!: Lord Katazyrna and Lord Bhajava, rulers of their respective domains and mortal enemies, are both driven, aggressive, and near-sociopathic in their disregard for the people around them. It's implied that Zan used to be a more self-aware, Pragmatic Villainy version of this as Lord Mokshi.
- Magnetic Hero: Zan's journey back up to the surface after being recycled sees her picking up several people that she meets along the way.
- Manipulative Bitch: Jayd all over the place, though she at least recognizes it and feels bad about it.
- No One Gets Left Behind: Zan eventually explicitly adopts this ethos, in stark contrast to her former persona, who had a much more I Did What I Had to Do attitude.
- One-Gender Race: As far as we're shown, the Legion is entirely populated by women. Rather than reproducing sexually, they appear to become pregnant spontaneously whenever their world needs them to produce a particular component, with each person specializing in a particular component (or rather, each womb; transplanting wombs with different production capabilities becomes a major plot point).
- Organic Technology: The entire Legion is built around this, to the point that the "passengers" themselves are part of their world-ships' systems, giving birth to necessary components. There seems to be some non-organic technology buried beneath it (such as the metal door that Zan finds), but it seems to be the exception rather than the rule.
- Planet Spaceship: In the language of the Legion, the word for "planet" and "ship" is the same. The techno-organic world-ships that make up the Legion are so massive that entire societies have developed in the depths who are unaware that there is a surface at all, let alone what goes on up there.
- Plot Coupon: "If you do not have the arm and the world, you need to begin again." They're the key to reviving the Mokshi and using it to leave the Legion.
- Wistful Amnesia: Despite not remembering their history, Zan retains an intense emotional attachment to Jayd and feels drawn to her despite not trusting her.