After his two-night killing spree in the first game, all charges against Max were dropped with the intervention of Senator Alfred Woden, per their agreement with the Inner Circle, aided by the mitigating factors of Max wiping out a sizeable amount of criminal organizations. In the two years since, Max (voiced by James McCaffrey) has left the DEA and returned to the NYPD as a homicide detective. During a seemingly routine murder investigation, Max discovers the 'Cleaners', a group of killers masquerading as a janitorial company to remove all evidence of their contract killings. During the ensuing shootout, Max briefly comes face-to-face with Mona Sax (voiced by Wendy Hoopes), a woman presumed dead from the first game. With Mona's reappearance comes the unsetting reminder of events he attempted long ago to bury, steamming from the drug Valkyr, the death of his wife and daughter, the Inner Circle, and his latent and uncomfortable feelings for Mona.
Upon returning to the station, Max eavesdrops on a phone conversation with his new NYPD partner, Detective Valerie Winterson, whom he suspects may be involved with hunting down Mona Sax. Moments later, the police station is attacked by people bent on killing Mona. After a series of chases to get to the bottom of the entire plot, Max ends up in a construction site. Mona helps him fight a series of battles, and the player gets to control her for a time while the AI controls Max whom the player has to defend.
Detective Winterson arrives and holds Mona at gunpoint; Mona says that Winterson is there to kill her. Max struggles with the dilemma, finally shooting Winterson and telling Mona to run. Assuming Winterson is dead, Max turns his back on her, but the fallen detective manages to shoot Max twice in the back which leads to the hospital scene where the player starts the game at before Max has his flashback. As Max and Mona fight for survival and answers, they discover that Vladimir Lem is behind the Cleaners' actions. Although Lem claims that he has given up crime to run a legitimate restaurant, he secretly controls the Russian Mafia in New York. He employs the Cleaners to destroy his competitors, including rival mob capo Vinnie Gognitti. When the Cleaners fail to eliminate Gognitti, Lem takes matters into his own hands and tricks Vinnie into donning an outfit of his favorite cartoon character, Captain Baseball Bat Boy. The oversized head of the outfit is rigged with a bomb that will explode if the head is removed; although Max protects Vinnie against waves of assassins, they are both captured upon attempting to locate Mona again.
Lem taunts Max, and reveals that Lem and Horne are both members of the Inner Circle, which Lem intends to seize control of following Woden's death. He also reveals Mona as a hired gun for Woden, with orders to kill both Lem and Max. Lem also accuses Woden of sending Horne's Valhalla files to the DA, an act which prompted Horne to kill Max's wife and daughter. Vlad shoots Max as revenge for killing Winterson, Lem's mistress, lodging a bullet in his head, before Lem kills Gognitti with a bomb and sets the hideout ablaze. As Lem leaves Max to die in the ensuing fire, Mona appears and rescues him. The two travel to Alfred Woden's manor to save him from Vlad, who intends to kill Woden and seize control of the Inner Circle. As they reach Woden's 'panic room', Mona confesses that her feelings for Max have restrained her from killing him. Suddenly Lem appears and shoots Mona, as Woden emerges from his sanctuary, using the opportunity to apologise to Max before lunging at Vlad, who shoots Woden. During the ensuing struggle, bombs placed throughout the manor are detonated, and Max chases Lem through the burning, collapsing mansion. Finally cornering Vlad above the sprawling main room of the mansion, Max dislodges the platform and mortally wounds Lem, who plunges to his death aboard the platform. As police arrive at the scene, Max returns to Mona, who dies in his arms. On the hardest difficulty setting, she survives. In either ending, Max finally finds some solace to his torment.