La historia comienza con un elite en armadura dorada, el antiguo comandante de la flota de naves Particular Justice siendo juzgado por los 3 Profetas lideres del Pacto en la ciudad flotante sagrada "Suma Caridad" por su incompetencia y su incapacidad de proteger la Instalacion 04 "Alpha Halo" de su destruccion a manos del Jefe Maestro en Halo Combat Evolved lo que termina en su exilio del Pacto y un castigo fisico. 

Mientras tanto el Jefe Maestro y el Sargento Johnson de nuevo en la tierra reciben condecoraciones por el almirante naval Lord Hood en la estacion espacial de la UNSC Cairo por la valeria de ambos en Halo mientras que Miranda Keyes, la hija del capitan Jacob Keyes que fue asesinado por los Flood recibe una medalla postuma por el valor y sacrificio de este.
 
Son interrumpidos por Cortana que les dice que una gran formacion de naves del Pacto han encontrado la tierra y se acercan a esta. El Jefe arriva a la ciudad de Nueva Mombasa en Africa donde la protege de los numerosos soldados del Pacto lo suficiente como para seguir a un crucero cargando al Profeta del Pesar a traves de un viaje al hiperespacio.

Los ojos cambian a los del desgraciado elite que es convertido subitamente en un guerrero santo del Pacto, "El Inquisidor" por los Profetas quienes le dicen que su primera mision es destruir una alianza hereje conformada por elites y grunts liderada por un elite renegado que se han separado formalmente del Pacto y se han atrincherado en una mina de gas Foreunner en el planeta Threshold. El lo consigue exitosamente matando al lider de estos y se encuentra con el monitor de Halo, 343 Guilty Spark quien tambien estaba ahi.

En un rincon lejano de la galaxia, la nave In Amber Clad pilotada por Miranda Keyes pasa por el agujero de gusano por hiperespacio siguiendo al Profeta Pesar, y descubren un segundo anillo "Delta Halo". Al aterrizar ahi el Jefe debe matar a Pesar que tiene planes de activar el anillo. El lo consigue pero una numerosa flota de los del Pacto y Suma Caridad llegan tambien a Halo, atacando al Jefe que cae a los profundo oceanos del anillo semimuerto.

En Suma Caridad despues de la muerte de Pesar por una orden de los Profetas restantes, Verdad y Piedad a los elites se les ha despojado su titulo de guardias de honor y en cambio este se le ha dado a los brutes, una nueva adicion militar de razas alienigenas al Pacto y al Inquisidor se le es asignado su proximo trabajo, entrar en la libreria Foreunner de Delta Halo y conseguir el Indice para poder activar la instalacion y comenzar lo que los Profetas llaman "El Gran Viaje". El facilmente derrota a Johnson y a Miranda quienes tambien habian entrado en esta para conseguirlo, pero es traicionado por el lider brute Tartarus, quien se apodera del Indice y con un poderoso impacto gravitatorio de su martillo "el Puño de Rukt" lanza al elite a las profundidades de la libreria.

El Jefe(con Cortana en su armadura) y el Inquisidor despiertan (ambos victimas de las acciones de los Profetas) prisioneros de una entidad inteligente Flood llamada "La Gravemind" quienes hablandoles (mediante las opiniones del monitor de Delta Halo "2401 Penitent Tangent" y el reanimado cadaver de Pesar a quienes ambos habia capturado) les dice que deben detener a los Profetas y a los brutes de activar Halo y los teletransporta a distintas partes. 


Al Jefe lo envia a Suma Caridad a parar a los Profetas de huir de esta y se encuentra en medio de una guerra civil entre las especies del Pacto, elites, grunts y hunters contra los brutes, jackals y drones. Eventualmente Cortana es insertada en las redes de Suma Caridad y la In Amber Clad tomada por los Flood se estrella en la ciudadela lo que termina en estos tomandola, en la muerte del Profeta Piedad y Verdad terminando como el unico Profeta vivo huyendo hacia la misteriosa nave Foreunner en el centro de la ciudad. El Jefe Maestro se infiltra en esta a medida que despega y deja a Cortana detras.

El juego concluye con las misiones del Inquisidor que con la ayuda del comandante de fuerzas especiales Rtas Vadumee y sus elites,(y formando una inesperada alianza con los humanos) mata a Tartarus(quien tenia prisioneros al sargento Johnson, a Miranda Keyes y a 343 Guilty Spark)antes de que pudiese activar Halo con el indice. Sin embargo antes el pudo poner este y los demas anillos esparcidos por las galaxias en un estado de activacion remota. 343 les dice que todos los anillos restantes pueden ser disparados desde el "Arca". En la tierra, la nave Foreunner ha llegado con un enorme ejercito del Pacto y el Jefe esta de polizon en esta con la intencion de "terminar esta lucha" como le dice a Lord Hood y a las demas fuerzas militares de la UNSC.

Despues de los creditos se muestra a Gravemind, que tambien ha llegado a Suma Caridad y tiene muchas preguntas sobre su origen y el de los anillos, por lo que cuestiona a Cortana que solo le responde "vamos, dispara", dejando una mirada previa a Halo 3

Y que hiso cortana durante ese tiempo?