The jury and court are swayed and Kirk and McCoy are found guilty. They are sentenced to the Klingon penal colony, Rura Penthe ("The Devil's Graveyard") a remote and frozen asteroid deep in Klingon space, where they will mine dilithium for the rest of their lives along with 1000s of other Klingon prisoners.
On the Enterprise, the bridge crew, at Spock's request, watches video of the torpedo hits to Kronos One. They determine that, though the memory banks of Enterprise show two torpedoes had been fired and that all the torpedoes they were carrying before the attack have been visually accounted for, the shots must have come from another ship. The only ship capable of remaining undetected would be one with a cloaking device, a Bird-of-Prey, which cannot fire while cloaked.
Spock ascertains, through the logical statement "once you eliminate the impossible, whatever remains, however improbable, must be the truth" that the Bird-of-Prey that fired on Kronos One can fire while cloaked. After further deduction, the crew knows what they must search for the two pairs of magnetic gravity boats worn by the assassins.
Kirk and McCoy arrive on Rura Penthe. They are told that nothing can survive on the surface due to extremely cold temperatures, and a prisoner is cruelly thrown outside to prove the warden's point, freezing in mere minutes.
A magnetic field above the asteroid prevents any unauthorized beaming to a ship. In the depths of the mine, Kirk is threatened by a large alien who demands his coat. Another prisoner, Martia, gets the thug to back off.
The crew begins to search every corner of the ship; as they do, they are continually contacted by Starfleet and ordered to return to Earth. Spock tells Scotty to report that the Enterprise is experiencing a warp drive malfunction. When Scotty begins to protest, Spock slyly tells them they need more time to search the ship. Scotty heartily says it could take "weeks" to repair.
Kirk finds himself in a fight with another huge alien who is easily winning the battle. Kirk kicks the beast in the knees and it falls down defeated. When he remarks he was lucky, Martia tells him that he kicked the creature's in the genitals.
Later, after they go to bed, McCoy relates their plight to the Kobayashi Maru test. Kirk theorizes that the incidents that led them to their imprisonment may have something to do with others who fear the peace accords with the Klingons. Suddenly, Martia appears and offers Kirk the chance to escape.
Chekov finds dried Klingon blood on the transporter pads and Spock says they will also search uniforms. A pair of gravity boots are found in the locker of Crewman Dax.
The next morning, Kirk and McCoy go to a meeting place arranged by Martia but do not see her. However, she is there, in the disguise of a large, hairy & ape-like alien.
Crewman Dax has been ordered to report and is accused of possessing the gravity boots, however his feet are largely different from human feet so the boots cannot be his.
Martia later changes to the form of a young human girl, allowing her to slip out of her shackles. She takes Kirk and McCoy through a hidden tunnel, changes back to the ape-like alien, leads to the frozen surface of the planet, and gives them warm winter clothing. They begin a lengthy march that will put them beyond the magnetic field covering the prison.
Back on the Enterprise, the signal from the device that Spock secretly placed on Kirk, a viridium patch, appears on a scanner and they set a course for Rura Penthe. In order to evade Klingon security outposts, Uhura, unable to use a universal translating device, must speak in Klingon. She is able to fool a sleepy guard at an outpost and the Enterprise continues to Rura Penthe.