Halo: Combat Evolvedin juoni sijoittuu 2550-luvulle, jolloin ihmiskunta ja sitä puolustava United Nations Space Command -järjestö ovat häviämässä sodan vihamielistä, avaruusolentojen muodostamaa Muukalaisliittoumaa (Covenant) vastaan. Pelihahmo on vihreään taisteluhaarniskaan pukeutunut kyborgisoturi Spartan-117 eli Master Chief, oikealta nimeltään John, joka on koulutettu taistelijaksi lapsesta alkaen muun muassa geenimanipulaation, vaativien taisteluharjoitusten ja monimutkaisten joukkuepelien avulla. Peliä edeltävät tapahtumat kerrotaan Halo: The Fall of Reach -kirjassa.
Varoitus VAROITUS: Seuraava kirjoitus paljastaa yksityiskohtia juonesta.
Pelin tarina alkaa, kun Reach-planeetalta Muukalaisliittouman joukkojen hyökkäystä pakeneva Pillar of Autumn -alus tekee valoa nopemman hypyn ja ilmestyy salaperäisen, renkaan muotoisen Halo-rengasmaailman lähettyville. Muukalaisliittouma seuraa pahoin vaurioitunutta alusta, ja lähettää joukkojaan vallatakseen Pillar of Autumnin.
Muukalaisliittouman ja United Nations Space Commandin sotilaiden taistellessa aluksen käytävillä, Pillar of Autumnia komentava kapteeni Jacob Keyes käynnistää niin sanotun "Cole-protokollan" (engl. Cole Protocol), jonka tarkoituksena on estää Muukalaisliittoumaa saamasta selville Maapallon sijaintia. Master Chief ja tämän taistelupuvun sisään siirretty "Pillar of Autumnin" luovaan ajatteluun kykenevä tekoäly Cortana pakenevat pelastuskapselin avulla rengasmaailman pinnalle. Myös Pillar of Autumnin miehistö onnistuu pakenemaan pelastuskapseleissa, vaikka suurin osa heistä menehtyy kapselien törmätessä maanpintaan. Heti Chiefin saapuessa planeetalle hän joutuukin aloittamaan UNSCin henkiinjääneiden sotilaiden pelastamisen Covenantien kynsistä Cortanan koettaessa paikantaa Keyesiä.
Samaan aikaan kapteeni Keyes ohjelmoi Pillar of Autumnin iskeytymään rengasmaailmaan, muttei ehdi paeta ajoissa alukselta joutuen Muukalaisliittouman vangiksi ja viedään Truth and Reconciliation -nimiseen Covenantien avaruusristeiljään. Master Chief kuitenkin onnistuu tunkeutumaan risteilijään ja pelastamaan kapteenin. Samoihin aikoihin Cortana saa selville, että Muukalaisliittouma pitää rengasmaailmaa pyhäinjäännöksenä, ja kutsuu sitä nimellä "Halo".
Cortanan mukaan Halo on suunnattoman tehokas ase, minkä vuoksi liittouma etsii rengasmaailman komentokeskusta. Keyes antaa Master Chiefille tehtäväksi paikantaa Halon komentokeskus ennen Muukalaisliittoumaa. Master Chief hyökkää ihmisjoukon kanssa saarelle, jossa Halon karttahuone sijaitsee ja paikantaa Halon komentokeskuksen. Master Chief tulee läpi planeetan ja hyökkää UNSCin tuella halki raskaiden Muukalaisliitouman varustusten saapuen Komentokeskukseen. Siellä Cortana ilmoittaa saaneensa selville, että Halolla on jonkinlainen salaisuus, ja että Keyesiä täytyy varoittaa tästä.
Master Chief tunkeutuu rakennukseen suon keskelle, jonne Keyes saapui pienen sotilasryhmän kanssa. Pian Master Chiefille paljastuu, että asevarastoksi luultu rakennelma olikin todellisuudessa tutkimuslaitos, jossa pidettiin vankina loiseliötä nimeltä Tulva. Tulva esiintyy aluksi pienehköinä itiöinä, mutta joutuessaan kosketuksiin elollisen olennon, jolla on tarpeeksi älyllistä kapasiteettiä ja biomassaa kanssa, itiö tarrautuu uhriinsa kiinni ja joko tappaa sen tai muuttaa sen zombimaiseksi mutantiksi, joilla kuitenkin on vaarallisen paljon älyä jäljellä, niin, että ne kykenevät ampumaan tarkasti ja ottamaan haltuunsa ihmisten ja Covenantien aseita ja laitteita.
Tulva leviää nopeasti Halolla tartuttaen lähes kokonaan jäljelle jääneet UNSC:n sotilaat ja huomattavan paljon Covenanteja. Poistuessaan tutkimuslaitoksesta Master Chief kohtaa suolla merkillisen 343 Guilty Spark -nimisen tekoälyn, joka kertoo olevansa Halon "valvoja". 343 Guilty Spark vie ilman Cortanan lupaa Chiefin maanalaiseen kirjastoon (engl. The Library) etsimään Halon laukaisuun tarvittavaa Indexiä. Kun Index löytyy Master Chief ja Guilty Spark palaavat takaisin Halon komentokeskukseen, ja tekoäly neuvoo häntä laukaisemaan Halon aseen, joka tuhoaisi Tulvan. Juuri ennen kuin Master Chief ehtii aktivoimaan Halon, Cortana ilmestyy ja kertoo hänelle totuuden: Halon ase ei hävitä Tulvaa, vaan kaikki älylliset elämänmuodot noin 25 000 valovuoden säteellä.
Tällä tavoin Tulva jäisi ilman "ravintoa" ja kuolisi hitaasti pois. Master Chief ymmärtää Halon aktivoimisen tuhoavan samalla ihmiskunnan, ja niinpä hän ja Cortana päättävät tuhota Halon. Master Chief lähtee komentokeskuksesta halki Muukalaisliittouman ja Tulvan välillä raivoavan taistelun tuhoten samalla Halon tuhoamiseen tarvittavia aktivointipisteitä.
Cortanan suunnitelman mukaan Halon pinnalle pudonneen Pillar of Autumnin fuusioreaktiorien ylikuumeneniminen aiheuttaisi ketjureaktion, joka tuhoaisi koko rengasmaailman. He kuitenkin tarvitsevat fuusioreaktorien aktivointiin kapteeni Keyesin hermoimplantteja. Cortana etsii Keyesiä ja paikantaa hänet jälleen The Truth and Reconciliationilta, mutta Tulvan hyökättyä alukselle siellä vallitsee kaaos.
Chief tunkeutuu jälleen monilta osin vaurioituneeseen risteilijään ja taistelun keskeltä löytää lopulta Keyesin, mutta tämä on joutunut Tulvan tartuttamaksi valtavaksi mutantiksi ja lopulta kuollut tuskiinsa. Master Chief pakenee Pillar of Autumnille, joka sekin on Tulvan ja Muukalaisliittouman välisenä taistelutantereena. Rikkoutuneen aluksen komentosillalle saavuttuaan Cortana käynnistää aluksen itsetuhon, mutta 343 Guilty Spark sammuttaa aluksen itsetuhojärjestelmän. Master Chief kuitenkin tuhoaa reaktoreiden jäähdytysjärjestelmän ja kaahaa karkuun aluksen tuhoa pelastautuen lopulta UNSCin sotahävittäjällä. Vaikka Cortana väittääkin hänen ja Master Chiefin olevan ainoat eloonjääneet, Halo: The Flood -kirjan mukaan myös kersantti Johnson sekä sotamiehet Locklear ja Polaski pelastautuivat tuholta Pelican-aluksella ja joukko Flood-olioita "Truth and Reconciliation"-risteilijällä.
Lopputekstien jälkeen nähdään lyhyt loppunäytös, joka paljastaa myös 343 Guilty Sparkin selviytyneen Halon räjähdyksestä.