Following the exodus from the Twelve Colonies, the human fleet has to make an FTL jump every 33 minutes to escape their Cylon pursuers, while the survivors cope with their losses and lack of sleep. After 238 jumps (five and a half days of pursuit), the civilian ship Olympic Carrier is mistakenly left behind with 1,345 on board; after 33 minutes, no Cylons appear, suggesting that they were tracking the Carrier. After the Carrier reappears followed by Cylons, Lee "Apollo" Adama and Kara "Starbuck" Thrace reluctantly destroy the civilian ship, believing it to be a threat to the rest of the fleet; the fleet finally escapes the Cylon pursuit. A copy of Number Six residing in Gaius Baltar's mind ("Inner Six") tries to convince him that God is watching over him, as one of the Carrier's passengers had previously planned to meet with President Laura Roslin, presumably revealing Baltar's role in the Cylon attack on the Colonies.

Multiple explosions on Galactica lead to the loss of 60% of the fleet's water reserves. Boomer experiences multiple blackouts where she suddenly finds herself soaked in water or carrying explosives without realizing how it happened; her secret romantic partner Chief Galen Tyrol helps her to avoid becoming a suspect in the explosion investigation. Commander William Adama suspects the involvement of a Cylon agent in the explosion and assigns Lt. Felix Gaeta to help Baltar speed up his work on the Cylon detector. During the water search, Boomer experiences another episode of unawareness where her ship detects water but she cannot properly read the reading and plans to detonate her ship instead, but later comes to her senses and reports her findings; the human fleet celebrates the water discovery. Roslin hires Lee as her military advisor.

Roslin and Commander Adama send a delegation led by Lee to the prison ship Astral Queen to recruit 1,000 prisoners to mine ice for the fleet. Tom Zarek, a renowned convicted terrorist, rejects the offer on behalf of all prisoners. Zarek and the prisoners start a riot, taking all the delegates hostage; Zarek demands Roslin's resignation and new elections. Starbuck leads an assault team to kill Zarek and free the hostages; before they succeed, Lee reaches an agreement with Zarek — the prisoners would end the riot and mine the water, but the government would hold elections in seven months. Meanwhile, Commander Adama gives Baltar a nuclear warhead to help him complete the Cylon detector.

After many of Galactica's pilots die in a deck accident, Starbuck begins training new ones. She is however conflicted as she still feels guilty about the death of her fiancé and Commander Adama's son Zak two years ago — being his instructor, she unfairly passed him in the basic flight test; this led to his death as he didn't have the necessary flight skills. Being overcautious, Starbuck washes out all of her new trainees after their first day of training. After she confesses to Adama about her role in Zak's death, he feels hurt and angered, but orders her to reinstate the trainees and resume the trainings. During another exercise, Starbuck and her trainees are attacked by a squadron of Cylon Raiders; humans defeat Cylons, but Starbuck's ship is heavily damaged and crashes to the nearby moon; Starbuck ejects into the moon's atmosphere. In Galactica's sickbay, Roslin visits doctor Sherman Cottle who confirms her diagnosis of advanced breast cancer and agrees to help procure "Chamalla" extract for her as an alternative treatment.

Continuing from the previous episode, Starbuck is stranded on a barren moon. Commander Adama directs all Galactica's resources to search for Starbuck, but they cannot find her, since the moon has a dense layer of clouds making its surface difficult to see. Starbuck finds a downed Cylon Raider from their previous confrontation. Having broken through the Raider's hull, she discovers it is made of living tissue in addition to mechanical parts; Starbuck uses it to replenish her oxygen supply and attempts to repurpose it for crewed flight. Roslin convinces Adama to call off the search operation after they estimate that Starbuck must have run out of oxygen by then, and agree that the continuing resource spending might endanger the entire fleet. As Galactica is about to leave the system, Starbuck appears flying the Raider and rejoins the fleet.

A copy of Aaron Doral commits a suicide bombing aboard Galactica. Roslin informs the entire fleet about the existence of humanoid Cylons, and Commander Adama appoints Sergeant Hadrian to lead an investigation of how Doral got aboard and got access to explosives. Since Tyrol and Boomer were having a secret romantic meeting at the time of the bombing, Tyrol's team tries to cover for them; Specialist Socinus, one of Tyrol's subordinates, is caught giving false testimony regarding Tyrol's whereabouts. After Hadrian puts Adama on stand and accuses him of covering for Tyrol and Boomer, Adama dissolves the tribunal and orders Hadrian confined. Roslin announces that Socinus was found guilty of negligence which allowed a Cylon to steal explosives. Trying to save Socinus, Tyrol confesses to Adama about his illicit relationship with Boomer; Adama refuses to hold Tyrol officially responsible as he is a more valuable crew member than Socinus — instead Tyrol's punishment will be his guilt for ruining Socinus's life. Tyrol ends his relationship with Boomer.

After Baltar mocks Six's belief in God, she disappears from his mind. A physical copy of Six appears on Galactica, introducing herself as "Shelly Godfrey" and accusing Baltar of sabotaging the human defenses before the Cylon attack on the Colonies. Baltar desperately tries to prove his innocence, but fails. After he prays to God and pledges himself to His will, Six reappears in his mind, and Gaeta, who was studying evidence presented by Godfrey, finds it to be fake; Baltar is released and publicly exonerated, while Godfrey mysteriously disappears from the ship. Meanwhile, Boomer helps Tyrol make progress in analyzing the Cylon Raider captured by Starbuck, and Roslin temporarily gets sick due to overdoing her anti-cancer medication, causing a brief fleet-wide scare.

A copy of Leoben Conoy is captured in the fleet after he appears in Roslin's dream. On Roslin's orders, Starbuck is sent to interrogate Leoben. Leoben tells Starbuck he planted a nuclear bomb set to explode soon. She tortures him for information about the bomb, but instead he talks about God, the soul and the cyclical nature of time. Leoben tells Starbuck that humans are destined to find Kobol and then Earth. After Leoben calls upon Roslin in her dream, she comes and promises him freedom. He reveals there is no bomb and tells her that "Adama is a Cylon". Roslin orders to put him out the airlock. Starbuck prays for his soul. Meanwhile, Boomer wants to prove to both herself and Tyrol that she is not a Cylon; she goes to Baltar to get tested. The test reveals that she is a Cylon, but Baltar, afraid of her reaction, tells her she is not.

Having completed work on the Cylon detector, Baltar begins testing the Galactica crew. Though she was presumed dead in the original Cylon attack, Colonel Saul Tigh's wife Ellen appears in the fleet. Since Commander Adama suspects Ellen, and Roslin suspects Adama and then Ellen of being Cylons, they give Baltar conflicting orders as to who to test first, frustrating him and interrupting and delaying his work multiple times. Mutual suspicions, Adama's concerns regarding Ellen's bad influence on Saul, and Ellen's erratic accusations against Adama of sexual harassment cause a quarrel between Roslin, Adama, Saul, and Ellen. The quarrel is resolved after Saul and Adama team up to repel an attack by a Cylon Raider and Baltar completes Ellen's test and declares her human. A conversation between Six and Baltar reveals that the result may have been fake and that Baltar would declare anyone human to avoid further fuss.

With the human fleet running dangerously low on "tylium", the main component of the fleet's fuel, humans discover a heavily guarded Cylon-controlled asteroid with large tylium deposits. The Galactica crew plan an ambitious operation to destroy the Cylon base and capture the asteroid. Baltar suggests hitting a specific spot to destroy the base without damaging the tylium ore, but does not know which spot to choose. Six advises him to seek guidance from God, and Baltar points to a random structure on the map. Mysteriously, he ends up being right; humans succeed and celebrate. Six tells Baltar that God ensured his guess to be correct. Meanwhile, Roslin hallucinates of snakes due to her anti-cancer medication. Priestess Elosha tells her about an ancient prophecy mentioning a "dying leader" who would bring humans to the new home.

To celebrate the anniversary of the Articles of Colonization, Roslin reconstitutes the Quorum of Twelve, a representative body within the Colonial government. Tom Zarek, who had called for Roslin's resignation, is nominated to fill the vacant role of Vice President. Worried that Zarek may try to assassinate her if he wins, Roslin initially drafts her friend and confidante Wallace Gray to run against Zarek. After Gray proves uncharismatic, she pushes him aside in favor of Baltar. Lee Adama and Starbuck arrest a man named Valance who has smuggled a handgun aboard Cloud Nine, the ship where the Quorum meeting is being held. They suspect that he may have ties to Zarek but find him dead in his holding cell in an apparent suicide. Baltar wins the election. Zarek warns Roslin he will be back during the presidential election in six months and claims he did not kill Valance.