Met Halo 3: ODST lanceert Microsoft dra een nieuwe Halo game welke het verhaal weer verder zal uitbreiden. Ondertussen is een groot deel van de gamers het volledige Halo reeds vergeten. Wij blikken daarom terug op het volledige verhaal van Halo.

Keyes verwacht een uitbrander, maar de admiraal feliciteert hem en promoot hem tot Commander. Keyes keert dan ook blij terug naar zijn appartement en zijn dochter Miranda. Ook Gray Team ontmoet Cole en zij krijgen tot hun grote vreugde een zeer gevaarlijke nieuwe missie.Op datzelfde moment ontmoet 'Vadamee en Zhar de Prophet of Truth en Regret die onthullen dat Truth en Regret niet samenwerkten waardoor zowel Reth als 'Vadamee dezelfde opdracht hadden gekregen. 'Vadamee kreeg zijn opdracht van Regret, waardoor zijn rechterhand ongerust is dat Truth voor zijn neus staat. Zhar denkt dat ze gedood zullen worden en hij trekt zijn zwaard. Onthutst door het gedrag van zijn vriend trekt 'Vadamee ook zijn zwaard en hij steekt Zhar neer. Regret is geschokt, maar Truth ziet geen probleem. Hij geeft 'Vadamee een schip in de Fleet of Particular Justice waarvan hij later Commander zou worden voor hij de rol van de Arbiter krijgt.

Tijdens de oorlog tegen de Covenant stierven vele Spartanen en het werd duidelijk dat het Spartan-II project heel duur bleek te zijn. Sommige missies waren zelfs voor de Spartan-II zelfmoordmissies. Rond 2535 besloot de UNSC dan ook om te beginnen met het goedkopere Spartan-III programma dat wordt beschreven in Ghosts of Onyx. Dit nieuw type Spartanen was vooral bedoeld voor missies met een grote kans op overlijden en er werd dan ook minder geld in hun training geïnvesteerd. De kinderen voor dit project waren allemaal kinderen van werelden die vernietigd waren door de Covenant en die voldeden aan een bepaald genetisch profiel. Zij werden getraind door Franklin Mendez, die ook de trainer was van de Spartan-II, en door de Spartaan Kurt-051 die hier de achternaam Ambrose kreeg. Hun training vond plaats op een menselijke kolonie genaamd Onyx waar ook verschillende Forerunner ruïnes aanwezig waren.

Deze nieuwe groep Spartanen was op zichzelf niet zo dodelijk als de oude Spartanen en daarom werden ze getraind als groepen. Op Gray Team na moesten de Spartan-II ook samenwerken, maar hun groepen waren veel kleiner. Wanneer ze voor het eerst ingezet werden in 2537 bleek het project een groot succes. Deze missie kostte wel het leven aan het volledige Spartan-III team dat werd ingezet tot grote horror van Kurt Ambrose. Ook de volgende missie van de Spartan-III kostte het leven aan honderden van de krijgers, maar twee van de driehonderd Spartanen overleefden de missie. De twee, Tom-B292 en Lucy-B091, bleken achteraf maar twaalf jaar oud te zijn en konden niet meer ingezet worden. Desondanks werd het project verder gezet. Door deze twee missies besloot Ambrose wel om de derde groep Spartanen (Gamma Company) illegale medicijnen toe te dienen om hen sterker in gevechten te maken. Dit gebeurde op 19 februari 2551.

In 2552 werd besloten dat de Aarde een vijandelijk schip moest veroveren en bestuderen om een kans te maken in de strijd. Hiervoor werd een team van Spartanen samengesteld onder leiding van Master Chief, kapitein Keyes en de technologie-expert Cortana. Met behulp van de Pillar of Autumn, dat bij zijn creatie niet meer dan een dure grap bleek te zijn, gingen ze de Covenant achterna. Wanneer het schip echter landde op de Reach vielen de Covenant hen aan. De Covenant waren in de meerderheid bij deze aanval en slaagden erin om de meeste mensen op de kolonie te doden. Zelfs de meeste Spartanen van Master Chiefs groep zijn gestorven bij de aanval. Master Chief zelf kan echter nog net ontsnappen door de slipspace met een kleine groep dankzij Cortana en de Pillar of Autumn. Dit is de aanloop naar het verhaal van de originele Halo en van het bijhorende boek Halo: The Flood.


De game begint wanneer de Pillar of Autumn uit de slipspace komt en belandt in een zonnestelsel van de Covenant. Daar vinden ze een rare constructie genaamd Alpha Halo dat een artificiële planeet bleek te zijn met zwaartekracht en allerlei vegetatie. Terwijl ze hier rondvliegen vallen de Covenant hen aan, maar zij zijn bang om het ruimteschip te vernietigen omdat de kolonie in de buurt hing. Hierdoor overleefde de Pillar de aanval, maar het schip was zwaar beschadigd en moest landen op Halo. Voor ze landden verliet Master Chief samen met de AI Cortana en enkele marinesoldaten het schip via een reddingsboei. Dat bleek hun redding te zijn want de Pillar of Autumn werd omsingeld door vijanden bij de landing en Kapitein Keyes werd gevangen genomen. Met de hulp van de soldaten bevrijdde Master Chief Keyes waarna hij Master Chief een nieuwe opdracht gaf.

Hij beveelt Master Chief namelijk om te ontdekken wat het doel van Halo is. Al snel komen Cortana en Master Chief aan bij het controlecentrum van Halo waar ze ontdekken dat de structuur is gemaakt door de Forerunners, een ras van uitgestorven buitenaardse wezens met geavanceerde technologie. Wanneer Cortana de computers van de Forerunners verkent, ontdekt ze een geheim van de Covenant en ze verplicht Master Chief om terug te keren naar Keyes terwijl zij verder onderzoek voert. Wanneer hij aankomt, ontdekt hij dat Keyes het slachtoffer is geworden van de Flood, buitenaardse parasieten, die bevrijd zijn door de onwetendheid van de Covenant. Op dat moment wordt Master Chief ingelijfd door de Forerunner computer 343 Guilty Spark om hen te helpen bij het stoppen van de Flood. Zij willen namelijk de Flood vastzetten op Halo en hiervoor moet Master Chief de Index zoeken, een apparaat dat alle wapens van de Halo kan activeren.