Two years prior, after the events of the previous game, Taiga Saejima agreed to return to prison and serve out the remainder of his term for the attempted murder of the Ueno-Seiwa Clan's leadership, despite the objections of his sworn brother, Goro Majima.

In 2012, Saejima is awaiting parole at Abashiri Prison in Hokkaido with his cellmates: Himura, a corrupt former police detective; Heihachiro Oshima, a professional thief; and Shigeki Baba, a former yakuza who killed a man for his aniki and took the fall. Despite being model inmates, Saejima and his cellmates are constantly harassed by Hiroshi Kugihara, another prisoner who has an inexplicable bone to pick with them.

Tensions escalate when Kugihara frames Baba for an attack on one of his cohorts. After Saejima, Himura and Oshima find proof of the set-up, they confront Kugihara and Saejima gets into a fight with him. After being beaten, Kugihara lets it slip that somebody instructed him to hound Saejima and goad him into fighting so that he would be denied parole.

Further bad news reaches Saejima soon after. When he and his cellmates are reading a newspaper, the top article informs them about the death of Goro Majima during an alliance negotiation with the Kitakata Family in Hokkaido, seemingly on the orders of the Family's patriarch, Taizo Kitakata.

A couple days later, Saejima is called to see the prison's warden, Seiji Kosaka. Kosaka informs him that, despite the fight with Kugihara, Kosaka still intended to recommend Saejima for parole, but unexplained orders came directly from the Ministry of Justice to deny Saejima's parole request. Not only that; an unusually large amount of yakuza inmates from other prisons were transported into Abashiri during the previous days. Kosaka suspects that somebody may be trying to make an attempt on Saejima's life. The warden, not wishing to allow assassins to carry out their dirty work in his prison, covertly passes Saejima a key to a snowmobile outside the prison, leaves Saejima's cell unlocked and encourages him to break out.

That night, Saejima makes a break for it with the help of his cellmates, taking Baba with him. However, their escape is hindered by Kugihara and the dozen new yakuza inmates who, as Kosaka correctly deduced, were transfered in to kill him. After an extensive battle, during which Kugihara is killed by Himura, Saejima and Baba manage to break out of the prison and flee into the wilderness with one of the guards' snowmobiles.

While fleeing across the snowy mountains, Saejima and Baba crash their snowmobile and are attacked by a gigantic bear. Saejima manages to beat back the beast and the duo are saved from the snow storm by a wandering hunter, who stumbles onto them while on a hunt and leads them back to his village.

After resting up for a couple of days, the pair continue to Sapporo.