L'histoire de Shadow of the Colossus commence quand Wanda traverse un grand viaduc pour entrer sur des terres interdites. Monté sur son cheval Agro, il arrive dans un énorme sanctuaire au centre de la région, puis dépose sur l'autel le corps enveloppé d'un linceul qu'il transportait. Il retire le drap et on découvre le visage d'une jeune femme nommée Mono. C'est alors que plusieurs créatures qui semblent formées d'un éther très sombre apparaissent pour attaquer les personnages. D'apparence humanoïde, les créatures-ombres sont rapidement vaincues par Wanda, armé de son épée.
Sortant des hauteurs du temple, la voix désincarnée d'une entité connue sous le nom de Dormin se fait entendre, surprise que le voyageur possède une telle arme. Wanda demande à Dormin de sauver son amie, en réintégrant l'âme dans son corps. Il lui explique que cela ne lui sera possible que lorsque les seize idoles de pierres du temple auront été détruites. Il lui faut pour chaque statue vaincre au préalable le géant qui lui est associé et qui repose quelque part dans la région. Pour cela, Dormin lui explique qu'il doit utiliser son épée, une arme unique aux pouvoirs magiques.
Malgré les avertissements de Dormin qui lui explique qu'il aura un grand prix à payer un prix pour réanimer Mono, Wander part à la recherche des colosses. Après la mort de chaque colosse, l'apparence physique de Wander se dégrade : sa peau devient plus pâle et ses cheveux plus foncés, tandis que Mono retrouve un teint plus frais.
Ce qui suit dévoile des moments clés de l’intrigue.
Après la mort du douzième colosse, apparaît aux abords du viaduc un petit groupe de guerriers dirigé par un chaman appelé Seigneur Emon; ils poursuivent Wanda. Exhorté à se presser dans sa tâche par Dormin, Wanda arrive bientôt au seizième et dernier colosse. Mais en chemin, alors qu'il traverse un pont, l'ouvrage s'écroule. Son cheval Agro a tout juste le temps de l'éjecter sur le versant opposé tandis que lui est emporter dans l'effondrement et tombe dans la rivière, des centaines de pieds plus bas.
Le groupe de guerriers arrive au sanctuaire alors que la dernière idole du temple se détruit. Wander apparaît peu de temps après, il a désormais un teint cadavérique et arbore deux petites cornes qui viennent de sortir de sa tête. Déclarant que Wanda est possédé, Emon ordonne à ses guerriers de le tuer . Alors qu'il tente de rejoindre Mono, un guerrier lui décoche une flèche à la jambe, tandis qu'un autre lui transperce le cœur d'une épée. Un sang noir s'écoule de la blessure, et le corps de Wander se couvre de ténèbres puis il tombe au sol (ainsi que meurent les colosses).
Dormin prend alors le contrôle de l'esprit de Wanda puis se transforme en un colosse-ombre. Il explique que son corps avait été séparé pour scellé son pouvoir. Alors que ses hommes fuient, Emon jette l'ancienne épée de Wander dans un petit bassin au fond du temple. Un tourbillon de lumière se crée et engloutit Dormin et Wander. Emon et ses hommes quittent alors les terres interdites, le viaduc qui permet d'accéder au temple s'écroule derrière eux. Comme ils arrivent en sécurité à l'entrée de la région, Emon espère que si Wander a survécu, il pourra un jour être en mesure de réparer ses actions.
Dans le temple, Mono se réveille, conformément à la promesse de Dormin, tandis que Agro la rejoint malgré une patte blessée. Ils s'approchent du bassin dans lequel Wanda et Dormin ont été aspirés, et y trouvent un jeune garçon avec des petites cornes sur la tête. Elle prend l'enfant avec elle, puis suit le cheval jusqu'à un jardin secret luxuriant, situé haut dans le sanctuaire.
