Halo Combat Evolved begins as the spaceship "Pillar of Autumn" is flying past a mysterious ring shaped space station named "Halo" by an alien race known as "The Covenant". A Covenant fleet attacks and heavily damages the "Pillar of Autumn". Captain Keyes, the captain of the Pillar of Autumn, initiates "The Cole Protocol", a procedure designed to prevent the Covenant frokm finding the location of Earth. While Keyes prepares to land the ship on Halo, the Master Chief (the main character) and Cortana, a holographic super-computer, escape via an escape pod, which crash lands on Halo. Master Chief and Cortana are the only ones who survive the crash.

Keyes survives the Autumn's crash landing, but is captured by the Covenant. In the second and third levels of the game, the Master Chief and Cortana gather human survivors and rescue Captain Keyes, who is imprisoned on the Covenant ship Truth and Reconciliation. Once rescued, Keyes orders the Master Chief to beat the Covenant to Halo's control center and to discover its purpose. The Master Chief and Cortana travel to a map room called the Silent Cartographer, which leads them to the control room. There, Cortana enters the systems and, discovering something urgent, suddenly sends the Master Chief to find Captain Keyes, while she stays behind. While searching for his commander, the Master Chief learns that the Covenant have accidentally released the Flood, a parasitic alien race capable of spreading itself by overwhelming and infesting other sentient life-forms. Keyes falls victim to them while looking for a cache of weapons. The release of the Flood prompts 343 Guilty Spark to recruit the Master Chief in retrieving the Index, a device that will activate Halo and prevent the Flood from spreading beyond the facility.

After the Master Chief retrieves and begins to use the Index, Cortana re-appears and warns him against the activation. She has discovered that Halo's defense system is a weapon designed to kill all sentient life in the galaxy, which the Flood need to spread. When confronted with this information, 343 Guilty Spark states that the installation technically only has a maximum radius of twenty-five thousand light-years, but that its pulse would trigger other similar installations as well, killing all sentient life in the galaxy.While fighting the Flood, the Covenant, and Guilty Spark's Sentinels, the Master Chief and Cortana attempt to destroy Halo before 343 Guilty Spark activates it. Cortana discovers that the best way to destroy Halo is to cause the crashed Pillar of Autumn to self-destruct. However, Captain Keyes' authorization is required to destroy the ship. By the time that they reach Keyes, he has been infected and turned into the Flood. The Master Chief retrieves Keyes' neural implants directly from his brain, and Cortana activates the Autumns self-destruct sequence. However, 343 Guilty Spark reappears and deactivates the countdown, discovering the record of human history in the process. The Master Chief manually causes the Pillar of Autumns fusion reactors to begin to melt down, and the Master Chief and Cortana narrowly escape the destruction of the ring via a fighter.