The Enterprise arrives at the planet Sarpeidon, as its star Beta Niobe is on the verge of going nova. The entire population of the inhabited planet has disappeared, and Kirk, Spock, and McCoy beam down to a building with a power source detected. The inhabitants had no space travel ability. Spock identifies the building as a library and an elderly man, Mr. Atoz comes in and identifies himself as the librarian. He's surprised to see them, mistaking them for inhabitants. He speaks vaguely of the people choosing from a wide number of options. He gestures them toward a series of shelves… and then appears from ahead of them. He suggests they look through the collection of recordings, but when they ask about recent history, Atoz directs them to the reference desk… and another Atoz.
Atoz berates them for being late and notes that everyone on the planet is now safe and the landing party had better do the same. He had his replicas handle the simple tasks while he evacuated everyone on the planet. Atoz plans to join his wife and family and turns down their offer of rescue. He shows them the library records, which contain detailed historical records of Sarpeidon. With three hours, thirteen minutes remaining, Atoz shows Kirk a viewer and brings up an image of an Elizabethan-like setting. Spock notices Atoz working a large computer device, the Atavachron. McCoy examines a disk that projects an ice field while Atoz explains that when they make their decision, he'll use the Atavachron to "prepare" them.
Kirk hears a woman's scream from an archway and rushes toward it. Atoz warns that he hasn't prepared them yet but Kirk enters the archway… and disappears. He finds himself in an alleyway where several fops are tormenting a woman. Spock and McCoy enter the arch and find themselves in the ice field McCoy viewed earlier.
Kirk comes to the woman's rescue and takes one of their rapiers to defend himself. He disarms the men and they run. Meanwhile, Spock discovers that his phaser doesn't work when he tries to heat the rocks. The woman comes on to Kirk and he suggests she come back to the library with him, but he finds nothing but a brick wall where he appeared. McCoy and Spock call out and Kirk hears them and vice versa. While the woman backs away in fear, Spock concludes the Sarpeidons escaped the nova by traveling back through time. They're unable to find a way back either. The fops arrive with the local constable and demand that Kirk be arrested. When McCoy calls out again, they suspect Kirk of witchcraft. He tries to follow their voices to the portal but they knock him out and take him away.
Spock and McCoy have no choice but to try to find shelter but McCoy soon collapses. He tells Spock to go on with him but the Vulcan refuses. A figure in furs confronts them and then leads them away to a heated cave. Spock makes McCoy comfortable and then speaks to their rescuer: a woman. She introduces herself as Zarabeth and identifies herself as a political prisoner sent through the portal by a dictator. She wonders if she's imagining Spock's presence as a hallucination brought on by loneliness, but he convinces her he's real.
The Prosecutor arrives to talk with Kirk in prison. He knows nothing of Earth but recognizes a reference to the library. The Prosecutor tries to get Kirk released but the woman, similarly imprisoned, insists that Kirk is a witch and blames Kirk for casting a spell and forcing her to steal. The Constable confirms the incident and Kirk explains, repeating that he came from the library. The Prosecutor hastily leaves, denying any knowledge of anything Kirk is talking about.
McCoy recovers conscious and an increasingly severe Spock explains what happened. When McCoy passes out again, he explains the situation to Zarabeth and asks her to show him the time portal. Spock has difficulty choosing logically between looking for Kirk and leaving McCoy behind. He asks Zarabeth how she cam there and she explains that her kinsmen tried to overthrow the dictator Zor Kahn and the tyrant banished all of their relatives. Spock asks her to help him bring McCoy through the portal. However, Zarabeth explains that she will die if she goes back through the portal due to the effects of the Atavachron. McCoy gets up and Spock explains that they are trapped in the past, unable to rescue Kirk.
In the prison, the woman is taken away for supper and a jailer gives Kirk a drink of water. He grabs the man through the bars and takes his keys, then knocks him out. He drags him into the cell and the Prosecutor comes down to visit. Kirk pretends the door is closed and tries to get the Prosecutor to admit he came from the future. Kirk opens the cell door and threatens to denounce the Prosecutor unless he helps. The Prosecutor explains that anyone prepared by the Atavachron for their new time period can't return to the future. Kirk realizes that he wasn't prepared and the Prosecutor warns he'll die in a few hours if he doesn't get back.
In the Ice Age, Zarabeth is preparing a meal and McCoy wants to look for Kirk. Spock notes that they can't go back and snaps at McCoy when he challenges the idea. When McCoy insults him, Spock grabs him and all but loses his temper. McCoy realizes what has happened to him.
Kirk returns to the brick wall and finds the portal. The Prosecutor flees and a weakening Kirk goes through, finding himself in the library in the present. With seventeen minutes left, Kirk finds no sign of Spock or McCoy. He finds Atoz, who offers to process him with the Atavachron and send him back. When Atoz tries to stop Kirk from interfering, he locks him up and knocks out another one. The real Atoz stuns him into unconsciousness
Zarabeth admits that she is glad she finally has company, and Spock sympathizes. She offers him cooked meat and he takes it, having no choice. Spock then admires Zarabeth openly for her beauty and realizes that something is wrong with him. He apologizes but again notes that she is beautiful, then kisses her and sweeps her off her feet, smiling.
Atoz attempts to push Kirk into the portal but he jumps clear of the cart at the last minute. The captain manages to overwhelm Atoz and force him to help look for Spock and McCoy. They go through the files looking for a frozen waste.
McCoy finds Spock and Zarabeth together in an embrace and questions his acceptance of Zarabeth's statement about their inability to return to their own time. Spock refuses to believe Zarabeth would lie but McCoy insists that she would do anything to ease her loneliness. Spock lashes out him and McCoy notes that at this time on Vulcan, Spock's people are violent barbarians. Now Spock is reverting to the same mind set. Zarabeth admits she doesn't know if they can go back, but she knows that she can't. McCoy insists that he'll try to find the portal or die trying. He goes out into the storm.
Meanwhile, Kirk has Atoz go through the data records and calls into the portal. Spock and Zarabeth go to help McCoy, and they hear Kirk call out. They follow his voice to the portal on their side. Spock tells McCoy to go without him so he can stay with Zarabeth. However, McCoy can't go through the portal alone: they went through together and have to go back together. With no other choice, Spock lets Zarabeth go and she looks on as the two men return tot heir own time. Atoz puts a disc of his own in and runs through the portal to his planned time. Spock assures McCoy that he is back to normal and whatever happened… happened five thousand years ago and Zarabeth is long dead. They beam out and warp out of the system as the star goes nova behind them.