Thus far, the storyline basically follows a human ship, the Pillar of Autumn, that attempts to draw the encroaching Covenant fleet , who have been cutting a bloody swath through human space, away from Earth and into some distant corner of the galaxy. This ship then enters the system containing the Halo, where a final battle is fought.

The player, a cyborg Master Chief aboard the Pillar of Autumn, takes the ship's AI, Cortana, and flees to the surface of the Halo with the Covenant in pursuit.

On September 21, 2001, a bungie.org reader named Chlazza found reference to a file called arrayxml.xml in the source code for the official Halo site. It described in detail a portion of the Halo backstory. This content was intended to be released in small portions over a period of time, and was subsequently removed from the official site. However, Chlazza posted it to the Marathon Story forum, and is still visible there.

It describes the development of spaceflight by the humans and the colonization of nearby space, the encounter with the Covenant, and ends with survivors from the Pillar of Autumn crashlanding on the surface of the Halo.

In a preview of Halo by GameSpot UK in late 2001, it was revealed that the Covenant in particular are interested in the Pillar of Autumn's AI, Cortana, which the player carries with him.