La historia de este capítulo de Tenchu sucede después de Tenchu: Fatal Shadows (aunque Fatal Shadows haya salido más tarde). Como en todos los demás episodios, el juego se basa en utilizar el sigilo y las técnicas ninja, de las cuales disponen nuestros personajes, y utilizarlas para realizar diversos tipos de misiones. Como personajes principales, nos encontramos nuevamente con Rikimaru y Ayame. También está la posibilidad de usar un nuevo personaje llamado Tesshu, que es un mercenario de noche y un doctor en el día.

La principal trama de Wrath of Heaven es nuevamente la aparición de Rikimaru y la introducción del mago Tenrai. Este es un malvado y sabio hechicero que dentro de sus artes ocultas posee la habilidad de devolverle la vida a las personas, pero él las usa para servirle de esclavos. Una de las personas que Tenrai revive es el Azuma ninja Tatsumaru, pero Tatsumaru todavía tiene sentimientos, ya que aunque su deber sea matar y detener el progreso de Rikimaru y Ayame a lo largo del juego, él no los quiere matar, porque dentro suyo reside el original Tatsumaru y no el amnesiado Seiryu. El verdadero objetivo de Tenrai es conseguir 3 joyas con cuyo poder, sumando el de Tenrai mismo, podría revivir al malvado Lord Mehio, dios del infierno. Sabiendo esto, Rikimaru y Ayame comienzan la búsqueda de las joyas de la Virtud, la Tierra y el Cielo.

• Rikimaru: el sobreconfiado del clan Azuma, portador de la espada Izayoi, nuevamente vuelve a protragonizar esta entrega. El ninja Rikimaru descubrirá gracias al aporte que le da Tatsumaru que, en su ojo derecho, el que Tatsumaru mismo le corta en Birth of the Stealth Assasins, se oculta el secreto del Dohjutsu, el ojo del ninja. Al progresar, Izayoi, la katana de Rikimaru, se dañará, por lo que tendrás que elegir si usar el metal de la Shichishito (la espada de Lord Mei-oh) o metales comunes para forjarla nuevamente (esto repercutirá en el final de juego).

• Ayame: la seria kunoichi, Ayame es la otra protagonista de Tenchu. Equipada junto con sus fieles espadas cortas, Ayame debe también conseguir las 3 joyas de poder para evitar que Tenrai reviva a Mei-oh. Ayame en una de sus misiones debe rescatar a Kiku, la hija de Lord Gohda, a quien ella prácticamente considera como su hermana pequeña, y la protege como tal.

• Tesshu: Tesshu Fujioka es el nuevo personaje jugable que se presenta en la saga. Es un doctor durante el día, pero por la noche, asume el rol de un asesino pago; un mercenario. Con una gran habilidad y conocimiento sobre artes marciales, Tesshu demuestra saber pelear y hacer buenas tomas hacia los enemigos.
• Onikage: también conocido como Suzaku en Birth of the Stealth Assasins, este misterioso demonio es otro de los personajes más importantes e interesantes de Tenchu. Prácticamente es imposible de morir, ya que siempre es resucitado por algún personaje con intenciones de usarlo como esclavo, pero al único al que siempre le rendirá culto y honores es a Lord Mei-oh.

• Tenrai: el malvado de la saga. Un hechicero con suficientes conocimientos sobre las artes ocultas como para revivir al mismísimo Lord Mei-oh. Este sabio mago es un hombre viejo y poderoso, tanto mental como físicamente. Intentará arrasar con Rikimaru y Ayame, pero juntos, con la ayuda de Tatsumaru, lograrán vencerlo.

• Tatsumaru: Exlíder del clan Azuma. Se suicidó con su propia arma empuñada por Ayame en Birth of the Stealth Assasins, Tatsumaru es traído nuevamente a la vida con los poderes de Tenrai, pero Tatsumaru arriesgará su vida para salvar a Ayame y Rikimaru, sin importar las órdenes de Tenrai.Como dato curioso cabe mencionar que el juego tiene varias referencias a la película de 1961 yojimbo

• Dr. Kimaira, Es un científico e inventor que se encuentra en el Amaig Clastle, una fábrica llena de trampas, quien pelea con una especie de marioneta gigante equipada con armas en su espalda.

• Kagura, Una astuta hechicera y aprendiz de tenrai. Al jugar con Rikimaru se le encuentra en el Bamboo Forest y pelea con Ganda, mientras que al jugar con Ayame se une con un zorro fantasma.

• Hyakubake Es un fantástico imitador quien lleva una caja que le da el poder de imitar a cualquier personaje, pero solo la apariencia no la personalidad ,realiza una copia idéntica de Rikimaru y Ayame.

• Ganda, Es uno de los hombres de Tenrai , quien se puede localizar en el Great Buddha temple.

• Jinnai, Un miembro del Muzen group, conformado por los gemelos Jinnai Ukyo y Jinnai Sakyo. Son asesinados por Tesshu.
• Hamada, Es uno de los hombres Lord Gohda. Rikimaru lo encuentra y lo mata sin pelear.

• Nasu, Un malvado político que se encarga de comerciar mujeres jóvenes, quienes son traficadas y vendidas por Tokubei Echigoya.

• Mr. D" CEO, Es el jefe de la malvada compañía CEO que se encuentra en la misión especial de Rikimaru titulada "Through the Portal". Rikimaru viaja al presente y se introduce a la corporación en donde encuentra este enemigo, para así deshacerse de él y su malvado plan.

• Tajima, Es un guardaespaldas que trabaja para Tokubei Echigoya, quien pelea con una katana y tres pistolas.