The opening scene shows previously unseen events taking place at the end of Final Fantasy VII. While Cloud Strife and his main party are in the midst of their final battle with Sephiroth to the north, Vincent Valentine and Yuffie Kisaragi are shown assisting the evacuation of Midgar as Meteor approaches the city. Shortly after the evacuation of the populace is complete Yuffie detects signs of life upon the Mako Cannon. Vincent instructs her to leave and rendezvous with Cloud and the party while he checks it out, knowing full well who is up there. Sure enough, Vincent arrives atop the cannon to find the near-lifeless body of Professor Hojo still slumped at the controls where he was left for dead after his battle with Cloud's group. Vincent prepares to finish Hojo off for good but his plans are scuppered as Meteor descends upon Midgar and begins tearing the place apart, forcing a hasty retreat from the city aboard a flying hoverbike piloted by Yuffie. As the two of them make their escape, a computer monitor on the Cannon's control panel shows that Hojo was able to upload his mind onto the World Network before the Meteor impact knocked it offline.

The game picks up again three years after the events of Final Fantasy VII. An unknown group of powerful SOLDIERs appear, bringing a swift and bitter end to the peace enjoyed by the people of world. The members of this enigmatic group are the ones who were trapped under the ruins of Midgar for three long years; the Deepground SOLDIERs, their intention is to call forth the final WEAPON, Omega, before its time. However, to do that, the DGS need Vincent to lead the way to Omega.

Vincent finds himself pursued by several elite members of the mysterious organization. An unrelenting chain of events leads Vincent to the truth behind his past and forces him once again to be the key player in a battle for the planet itself and all those living in it. Reeve Tuesti, former Head of Urban Development at Shinra (as well as the remote pilot of Cait Sith), is now the leader of the World Regenesis Organization, which looks after the planet and prevents people from damaging it further. Yuffie Kisaragi is another member of the organization, and several other characters from the original game provide the WRO with outside assistance.

The game begins with an FMV depicting the attack on the town of Kalm, an attack carried out by Deepground soldiers. Vincent thwarts the attack, but not before encountering Azul and Shelke, members of the Tsviets, Deepground's elite force of supersoldiers.

Vincent makes his way through Kalm, taking down the Deepground soldiers, and saving many of the Kalm town's people from being killed or kidnapped. As Vincent reached the town centre, a Deepground helicopter, called Dragonfly, attacks. Vincent fights it off, and makes his way into a nearby residence where he meets Azul, and an endless amount of soldiers. Vincent must now meet Reeve at the church, and heads back through Kalm, assisting the WRO on the way. As he reached the church the Dragonfly returns, this time known as Dragonfly GL. Once it is taken down, Vincent and Reeve meet, and the mission ends.

As Vincent and Reeve speed across the desert to Edge, Reeve tells Vincent about the Deep Ground soldiers, and that they were a secret project that only President Shinra, Heidegger, Scarlet and Hojo knew about. When Rufus took over after his father's death, the ascension was so quick that he didn't have a chance to be told about the Deep Ground soldiers, and the deaths of the other Shinra executives eliminated all outside knowledge of the project, causing the soldiers to languish in the research facility for three years.

Reeve then tells Vincent that 1200 people disappeared from Junon. The conversation is then interrupted by a transmission from a mysterious figure that states his desire to 'cleanse' the world, and the tainted shall be killed. After the transmission ends, the van is attacked by Guard Hounds. Vincent saddles up on the machine gun and fends them off before making his way on top of the van, where he continues to defend it with his own firearms. With the van damaged, Vincent is forced to make his way to Edge by foot while under constant assault from more Guard Hounds and their pack leader, Crimson Hound. Near the entrance to Edge, he is confronted again, this time by several Deep Ground soldiers on bikes. After defeating the soldiers, he crosses the border into Edge.

Rosso sits on a crate in a factory laughing to herself about Weiss' talk, then the camera zooms out to show dead WRO members surrounding her. Vincent is peering around a corner, when a woman wearing a labcoat points her gun at his head, but he turns pointing his gun at hers. He notices a WRO badge and puts his gun down. She introduces herself as Shalua Rui. Shalua says that Edge is too quiet, and that the WRO troops and 500 townspeople are nowhere to be seen. She then walks off talking about finding her 'reason to live.' Vincent fights his way through town, and finds a dying WRO member, who mentions a soldier in red and a warehouse at the edge of town, before dying. Eventually, he makes his way into a central area, where he takes down many snipers around the area, and saving a child, who leads him to someone who has a card key to get into the warehouse. In the warehouse Vincent must fight a Heavy Armoured Soldier. Rosso is outside, and calls Vincent the 'Keeper of the Protomateria.' The two fight, and she smashes Vincent into the wall, where he begins to glow red and transforms into Chaos. He knocks Rosso away, and then falls to the ground, Shalua coming up behind him.

The scene switches to a flashback, with Vincent in Lucrecia's cave, she keeps saying 'sorry' and Vincent questions why. The scene then goes further back to when Vincent was a Turk, and is arguing with Hojo. It ends in Hojo shooting him, and then muttering to himself about experiments. When Vincent eventually awakens, he stumbles, and falls before it fades to black, Vincent screaming. The final flashback, shows him in regenerative tube, with Lucrecia looking in on him.