It has been a year since Kirito cleared Sword Art Online, but dangers continue to plague VRMMO games. One day, Kirito is approached by Seijiro Kikuoka, a government agent who investigated the SAO incident, with a favor to ask: someone has been committing murders from a popular new VRMMO, Gun Gale Online, and he wants Kirito to investigate. While Kirito is reluctant to oblige Kikuoka, the thought of someone being able to kill people from within a VRMMO troubles him, so he ultimately agrees to investigate.
Within GGO, he meets another player, a sharpshooter named Sinon. In the real world, Sinon's player, Shino Asada, had been involved in a robbery as a child during which she wrested the gun from the criminal and shot him to death. Although she had acted in self-defense, the trauma from the incident, combined with bullying and ostracization by her family and peers, has caused her to suffer panic attacks when in the vicinity of guns, real or model; even someone pointing at her with a gun-like gesture is enough to trigger her. She had taken to playing GGO as a means to try and cure her phobia, and hopes that winning the upcoming tournament, the Bullet of Bullets, will give her the strength she needs to overcome her weakness.
Kirito finds that he has a hard time using guns in GGO, but manages to find a weapon that is ideal for his playstyle; a Photon Sword. He enters into the BoB tournament with Sinon in the hopes of finding the killer, who seemed to be targeting the highest-level players in the game.
During the preliminaries, Kirito comes face-to-face with the player believed to be the murderer, who refers to himself as "Death Gun". The killer asks Kirito if he is the "real deal", revealing a tattoo on his arm that belonged to Laughing Coffin, a player-killing guild from SAO. Kirito realizes that the killer is an SAO survivor like himself, and recalls a forgotten memory of a multi-guild effort to dismantle Laughing Coffin. During the skirmish, Kirito killed several Laughing Coffin members, but he couldn't remember the names of any of the player-killers he fought, leaving him greatly troubled.
As the tournament enters the finals, Kirito and Sinon decide to work together to try and defeat Death Gun. However, Death Gun manages to ambush Sinon. As he prepares to kill her, Sinon recognizes the pistol Death Gun used in his killings as the same one from her childhood, scaring her to her very core. Kirito manages to rescue her, however, and the two take shelter in a cave. Sinon confides in Kirito her fear of guns and her traumatic childhood, while Kirito deduces the killer's methods; rather than being one person, Death Gun was at least two people. One played the game as Death Gun while the other broke into the homes of their targets and injected them with poison after the player shoots their avatar.
Kirito and Sinon team up to draw out Death Gun. After Sinon destroys Death Gun's rifle, Kirito engages him in close quarters. When Death Gun starts using an estoc to fight him, Kirito recognizes him as a Laughing Coffin member, Red-Eyed XaXa. Kirito eventually manages to land a killing blow on Death Gun, and he and Sinon end the tournament in a draw.
When Sinon logs out, she is greeted by her classmate, Kyoji Shinkawa. Unfortunately, Kyoji reveals himself to be one of the collaborators behind "Death Gun", modeling his gun after the one from Shino's childhood in a sick show of his affection for her. When Kyoji tries to force himself on her, Shino fights back, and Kirito arrives at her apartment to help her subdue Kyoji.
Afterwards, it was revealed that Kyoji was the younger brother of an SAO survivor who was a member of Laughing Coffin. Kyoji cooperated with his brother, along with another SAO survivor and Laughing Coffin member, to give rise to "Death Gun", originally conceived as a means of getting revenge against another player who tricked Kyoji into making a sub-par character build. Kyoji and their collaborator were now confined to psychiatric hospitals, but Kyoji's brother, Shouichi, remains at large...
Afterwards, Kirito invites Shino to meet one of the survivors of the robbery she thwarted. The survivor thanks Shino for that fateful day; if not for her deeds, neither she nor the daughter she was pregnant with at the time would be alive. Realizing the positive effects she had on the day she shot the robber, Shino is finally able to let go of the past.
