The Enterprise enters the Beta Niobe star system, where the star is about to go supernova in a few hours.
The starship approaches Sarpeidon, a class-M planet in the system, and Captain Kirk (William Shatner), Mr. Spock (Leonard Nimoy) and Dr. McCoy (DeForest Kelley) beam down to investigate a technological center
They enter a library building, and find a most unusual librarian, Mr. Atoz (Ian Wolfe), who tends to a machine called “the Atavachron” and insists that they select “verism tapes;” discs in the library which showcase different historical eras of Sarpeidon.
After accessing one tape -- of a time period resembling 17th century England on Earth -- Captain Kirk hears a woman’s scream, and races through a doorway that is actually a time portal. Dr. McCoy and Spock race after him, but because McCoy was studying a tape of the Sarpeidon ice age, end up in a frozen wasteland.
Trapped in different time periods, the Starfleet officers must find their way back to the library, as the clock ticks down towards supernova.
In the ice age, Spock and McCoy encounter a lonely woman, Zarabeth (Mariette Hartley), who was exiled there by a tyrannical leader. Spock, who is becoming more like the Vulcans of Zarabeth’s time period, 5000 years in the past, experiences a strong emotional connection to the woman. They fall in love.
However, Zarabeth can never return home to her time period, because of preparation through the Atavachron. She is doomed to spend the rest of her days in this frigid, frozen world.
Meanwhile, Kirk makes his way out of a prison, after being accused of witchcraft, and returns to the library. There he grapples with Mr. Atoz, who desperately wants to prepare Kirk, and then escape to his own “yesterday.”
“All Our Yesterdays” is a beautiful and successful Star Trek love story, from a season featuring too many weak love stories (“For the World is Hollow and I Have Touched the Sky,” “Requiem for Methuselah,” and “The Lights of Zetar.”)
The fact that this episode succeeds so ably is even more surprising considering that the character who falls in love is the unemotional Mr. Spock. Spock love stories are difficult to write well, and yet this story, from Jean Lisette Aroeste, is elegant and haunting.
Fortunately, a "logical" reason is given for Spock’s unusual emotional attachment. Upon returning to the past, he begins to act in the emotional, savage manner of Vulcans of the time period; pre-Surak. This idea is a wonderful addition to canon, and augments the already-established suggestion that Vulcans can sense each other over long distances, in the form of light telepathic contact (a factor also made evident in “The Immunity Syndrome,” and recently in Star Trek: Discovery’s  “The Battle of the Binary Stars.”)
Given this mental connection to the Vulcans of 5,000 years in the past, it is natural and makes sense that Spock begins to behave in a different fashion, showing signs of emotion, falling in love, and eating animal flesh. I only wish there were as strong an explanation for Kirk’s behavior with Rayna in “Requiem for Methuselah,” or Scotty’s out-of-character actions in “The Lights of Zetar.”
Spock himself makes note of the changes in his character, and at one point nearly even kills the argumentative McCoy. When McCoy calls him a name, Spock nearly strangles him, saying he doesn't like it, and never did.
Despite the outside forces working on the beloved character, the love between Spock and Zarabeth nonetheless feels absolutely authentic (again, something that can’t be said of the love stories in the other episodes I mentioned). Zarabeth is intelligent and strong, and alone. These are qualities that Spock might very “logically” feel himself drawn to. After all, he is an outsider among other humans, very much alone in some important ways.
The love story is made all the more touching by two factors at the end of the tale. First, Spock must leave Zarabeth, if McCoy is to go home. So, Spock must deliberately act against his desire and will to remain with Zarabeth, in essence stranding her alone all over again.
And secondly, after he steps through the time portal, Spock returns to normal, and shows no sign of his previous attachment to Zarabeth. He is his "cool" unaffected self again.
Of course, we know Spock better than that. There is no doubt he remembers and still feels something powerful for Zarabeth. It is just that, in the present, he is better able to suppress his emotions.
For me, this haunting ending, with Spock coldly disavowing his former emotional state, ranks right up with the codas of “City on the Edge of Forever” (Kirk’s “Let’s get the Hell out of here”) and “This Side of Paradise” (Spock’s “For the first time in my life…I was happy.”)
The tragic nature of this story is beautifully depicted by both Leonard Nimoy, as the confused and befuddled Spock, and Mariette Hartley as the lonely, desperate Zarabeth. It is a testament to both performances that this love story feels so real, and so, well...star-crossed.
If Spock’s story in “All Our Yesterdays” feels powerful and authentic, Kirk’s story proves markedly less interesting. He must battle accusations of witchcraft, and win over the trust and aid of the local prosecutor (Kermit Murdock), who is also a time traveler. The tale isn’t particularly interesting, but matters for Kirk grow even more intense upon his return to the library, and his battle of wills against Mr. Atoz and his duplicates.
Indeed, Kirk’s story becomes increasingly tense as the supernova event nears, and he must desperately attempt to locate Spock and McCoy…somewhere, in all of the planet’s history. At one point, Atoz gets the jump on Kirk, “prepares” him through the Atavachron, and nearly dooms Kirk to a life spent in the past. These moments are very suspenseful.
The Zarabeth-Spock love story, however, ultimately became so beloved by Star Trek fans that A.C. Crispin continued the tale of their affair (and its aftermath: a child) in the novels Yesterday’s Son, and Time for Yesterday.
Less remarked upon, but no less interesting is the sci-fi idea put forward cleverly by this episode, that to travel through time -- and survive in another age -- a person must be physiologically prepared for their new home. Their cells, essentially, must be altered.
I rather like this detail in "All Our Yesterdays," as it would preclude time travelers from moving, en masse into previous ages, and polluting a time-line. I would love to see Star Trek pick up this idea on a more recurring basis, since it suggests that time travelers can only exist for a matter of days in another era, before exposure to that age (and that age’s diseases?) kills them. So, the events of many movies and episodes could still occur, but there would be regular danger for time travelers, if they overstayed their welcome.
Next up, the final episode of Star Trek: “Turnabout Intruder.”