The Stars My Destination is the science fiction story of revenge-driven escaped prisoner Gully Foyle, an analogue to Alexander Dumas' Count of Monte Cristo. Foyle remakes himself to seek revenge on a former employer, a powerful corporation which ignored him after the wreck of his cargo ship. The plot also deals with how jaunting, the ability to teleport matter through space, has destabilized human society throughout the galaxy and on Earth, now called Terra.
In the 25th century, "jaunting"— personal teleportation — has so upset the social and economic balance that the Inner Planets are at war with the Outer Satellites. Gully Foyle of the Presteign-owned merchant spaceship Nomad — an uneducated, unskilled, unambitious man whose life is at a dead end — is marooned in space when the ship is attacked and he alone survives. After six months of his waiting for rescue, a passing spaceship, the Vorga , also owned by the powerful Presteign industrial clan, ignores his signal and abandons him. Foyle is enraged and is transformed into a man consumed by revenge, the first of many transformations.
Foyle repairs the ship, but is captured by a cargo cult in the Asteroid Belt which tattoos a hideous mask of a tiger on his face. He manages to escape and is returned to Terra. His attempt to blow up the Vorga fails, and he is captured by Presteign. Unknown to him, the Nomad was carrying "PyrE", a new material which could make the difference between victory and defeat in the war. Presteign hires Saul Dagenham to interrogate Foyle and find the ship and PyrE.
Protected by his own revenge fixation, Foyle cannot be broken, and he is put into a jaunte-proof prison. There he meets Jisbella McQueen, who teaches him to think clearly, and tells him he should find out who gave the order not to rescue him. Together they escape and get his tattoos removed— but not with total success: the subcutaneous scars become visible when Foyle becomes too emotional. They travel to the Nomad , where they recover not only PyrE, but also a fortune in platinum. Jisbella is captured by Dagenham, but Foyle escapes.
Some time later, Foyle re-emerges as "Geoffrey Fourmyle," a nouveau riche dandy. Foyle has rigorously educated himself and had his body altered to become a killing machine. Through yoga he has achieved the emotional self-control necessary to prevent his stigmata from showing. He seeks out Robin Wednesbury, a one-way telepath, whom he had raped earlier in the novel, and persuades her to help him charm his way through high society.
Foyle tracks down the crew of the Vorga to learn the identity of the ship's captain, but each is implanted with a death-reflex and dies when questioned. Each time, Foyle is tormented by the appearance of "The Burning Man", an image of himself on fire.
At a society party, Foyle is smitten with Presteign's daughter Olivia. He also meets Jisabella again— now Dagenham's lover — who chooses not to reveal Foyle's identity, although Dagenham has realized it anyway (Foyle's alias was implanted in his subconscious mind during Dagenham's interrogation). During a nuclear attack by the Outer Satellites, Foyle goes to Olivia to save her. She tells him that to have her, he must be as cruel and ruthless as she is.
Robin, traumatized by the attacks, tries to buy her way out of her arrangement with Foyle with the name of another Vorga crew member. Foyle agrees, but immediately reneges. In response, Robin goes to Central Intelligence to betray him. Bester once wrote that he used playful narraration at one point to grab the readers attention.
Foyle learns that the captain of the Vorga joined a cult on Mars and has had all her sensory nerves disabled, making her immune to conventional torture. Foyle kidnaps a telepath to interrogate the captain, and learns that the ship did not rescue him because it was picking up refugees, taking their belongings, and scuttling them into space. He also learns that Olivia Presteign was the person in charge. Olivia rescues him from Martian commandos, as she sees in Foyle someone who can match her hatred and need to destroy.
Driven by a guilty conscience, Foyle tries to give himself up, but is captured by Presteign's lawyer Regis Sheffield, who turns out to be a spy for the Outer Satellites. Sheffield tells Foyle that when the Nomad was attacked, Foyle was taken off the ship, transported 600,000 miles away, and set adrift in a spacesuit to be a decoy to attract ships to be ambushed. Instead, Foyle space-jaunted — a previously unknown possibility — back to the Nomad . Now, the Outer Satellites not only want PyrE, they want Foyle as well, to learn the secret of space-jaunting.
Meanwhile, Presteign reveals that PyrE is activated by telepathy, and Robin is enlisted to trigger it to flush out Foyle. Bits of PyrE left exposed by Foyle's tests into its purpose cause destruction worldwide, but primarily at Foyle's abandoned encampment in St. Patrick's Cathedral, where Sheffield has brought him. The church partially collapses, killing Sheffield and trapping Foyle, unconscious but alive, over a pit of flame. Suffering from synesthesia brought on by the explosion affecting his neurological implants, Foyle jauntes through space and time as The Burning Man. Finally he lands in the future, where Robin telepathically tells him how to escape from the collapsing cathedral.
Back in the present, Foyle is pressured to surrender the rest of the PyrE, which was protected from exploding by its Inert Lead Isotope container, and to teach mankind how to space-jaunte. He leads them to where the rest of the PyrE is hidden, but makes off with it and jauntes across the globe, throwing slugs of PyrE into the crowd at each stop. He asks humanity to choose: either destroy itself or follow him into space.
Foyle now realizes the key to space-jaunting is faith: not the certainty of an answer, but the conviction that somewhere an answer exists. He jauntes from one nearby star to another, finding new worlds suitable for colonization, but reachable only if he shares the secret of space-jaunting. He comes to rest back with the cargo cult, where the people see him as a holy man and await his revelation.