A Japanese businessman, Rokuro Okajima, finds himself in the grasp of a mercenary group known as Black Lagoon. They have captured him in order to take a disk of company secrets that he was transporting. The company responds to the capture by sending a 'military for hire' after them to eliminate him and the disk.

The Lagoon - the mercenaries' PT boat - is chased into a river by the military forces, which are chasing primarily in an attack helicopter. It seems the lightly-armed Lagoon has no chance against the helicopter, but Rokuro formulates a plan involving the boat's torpedoes and a partially-sunken ship lodged in the river canal. After defeating the helicopter, the Black Lagoon brings Rokuro to the realization that he has been written off by his former employer. He elects to stay with the mercenaries, who start to call him by the nickname 'Rock'.

Roanapur is the south Pacific city in which the Black Lagoon operates as 'Lagoon Trading Company', and in which many crime syndicates operate. One of the crime lords, Mr. Chin, takes exception to his former colleague Dutch (leader of Black Lagoon) working for the Russian mafia, Hotel Moscow, operated by a former Soviet military officer known only as Balalaika. To that end, Chin sends a pirate gang after the Black Lagoon while they are at sea. Through gun-woman Revy's skills, Lagoon defeats the pirate gang, and back in Roanapur, Balalaika personally takes care of Mr. Chin's involvement in the crime world permanently.

The Lagoon Company is hired by a collector of Nazi art to recover a painting from a sunken German U-boat. Revy and Rock descend to the U-boat in scuba gear, while the Black Lagoon is attacked by neo-nazis on the surface.

Dutch and Benny are kept at bay by the neo-Nazi ship on the surface, having to dodge a series of TOW missiles, while Rock and Revy continue to fight the intruders both inside the downed sub and underwater.

Dutch takes Revy over to the neo-Nazi ship in order to finish the fight. Revy, incensed by Rock's actions in the previous episode - where he restrained her from going into a definitely suicidal battle with the undersea attackers - goes on a killing spree. Dutch stops her just before she gets to the innocent hired crew of the ship, and straightens her out. Finding the boss of the neo-Nazis, he then discovers that the man who hired him is a Nazi himself, and hired both him and the neo-Nazi group to recover the painting and test the neo-Nazi group's competence. When the whole affair is over, Revy, back on the Lagoon, tells Rock that since he is different from them - mainly referring to his conscience - that she can't work with him any more.

Dutch sends Rock on errands around Roanapur - mainly collecting on owed bills and such - and orders Revy to accompany him. Revy gives Rock grief about his conduct, saying he's not able to hack this life and should go back to Japan. Rock finally snaps and chews Revy out about her attitude, and in return, she tries to shoot him at point-blank range. The police come in response to the ruckus being raised in the center of town, and arrest both of them - though it will be only symbolic, as the police are corrupt and in league with all the syndicates anyway. In the police car, Rock and Revy, now calmed down, come to an understanding about one another.

Lagoon is hired to deliver a package, consisting of a boy - the son of a high-profile Venezuelan crime family. Colombian crime lords in Roanapur find that he is in the city and try to take him out, but his maid/bodyguard Roberta arrives in town at that point. Lagoon arrives at their favorite watering hole - a bar called Yellowflag - just as Roberta confronts the Colombian mob inside.

The maid Roberta starts destroying Yellowflag, and everyone in it. In the ensuing battle, Revy is knocked unconscious. Lagoon flees, and the boy, Garcia, goes with them, being afraid of the violent person his maid and friend Roberta has become. Roberta pursues, her methods quite reminiscent of the Terminator (and remarked as such by Rock during the chase).

Revy finally regains consciousness and enters into combat with Roberta. The battle is violent, and very balanced at the same time, neither woman gaining the upper hand. Balalaika arrives, surrounding the group with a small army, forcing an end to the fight - for a moment - while she exposits that Roberta is actually an elite ex-resistance fighter from a group of South American rebels. Balalaika strips the duo of their weapons, and they go at it with their fists. This is again interrupted when Garcia begs for Roberta to stop, and he will go home with her.

Chang, leader of the Hong Kong triad, comes to Lagoon wanting their assistance transporting some documents belonging to anti-US terrorists - which Chang recovered and is selling to US interests. Rock and Revy are enlisted to do the job, and are supposed to rendezvous with another group - Shenhua, a Taiwanese assassin, and her partner Leigharch, a drug-dealing European man - on an island in the Philippines. Upon their arrival there, Rock ends up captured by the terrorist group, who got to he and Revy just before Shenhua and her colleague arrived.

Season finale. Rock is interrogated by a Japanese man involved with the terrorist group. Revy, entering into a partnership with Shenhua, despite the fact she can barely tolerate the woman, makes plans to raid the terrorist camp and recover Rock. A tremendous battle ensues, with the entire terrorist group chasing the foursome all the way up to the de-militarized zone where the CIA is waiting for the papers. As they arrive, Rock realizes with a panic that the briefcase he'd been carrying was left behind in the terrorist stronghold. Revy tells him not to worry, and pulls the papers out of her shirt, where she'd been hiding them all this time - revealing that she went back to the stronghold to rescue Rock, not for any other purpose. Upon handing over the papers, the Americans give one last parting shot to Revy - calling her "Miss Rebecca", revealing her real name, and telling her that both the Buffalo, NY PD and the NYPD 27th Precinct are still on the lookout for her - a reference to her violent childhood growing up in the United States.

Mysterious killings of various gangsters are occurring in Roanapur. Hotel Moscow investigates the murders to take revenge, and bounty hunters from all over the world come to collect on the bounty Balalaika offers in Roanapur.

Hotel Moscow finds out who the killers are, and sets up a trap for them. However, Revy and Eda have other plans that might cross paths with Hotel Moscow.

Balalaika exacts her revenge against the killers, even as one seeks the aid of the Lagoon Company.

A fugitive counterfeiter named Jane arrives at the Church of Violence, hoping to find shelter. When the bullets start flying, prayer probably won't help - but Revy and Eda might.

The bounty hunters arrive at Jane's motel, and she escapes due to preparations Eda had made beforehand. Jane sees Eda and agrees to pay any price if Eda saves her. Eda and Revy force the bounty hunters to retreat and begin heading to the Black Lagoon. When Russel arrives at the scene, Shenhua demands more money since Eda and Revy are involved. Eda's plan to escape on the Black Lagoon is stymied since Dutch and Benny took it on a job, and they are forced to wait in the Lagoon Company dock house. They are attacked by the bounty hunters, who surround the building. As Shenhua and Sawyer arrive, Revy curses their misfortune, and Rock and Jane are forced to head to the roof when building is set on fire. Meanwhile, Dutch begins speeding back into port and Revy sets a trap for Shenhua.

Shenhua evades the trap, but is shot by Eda after Revy acts as a decoy. On the roof, Rock and Jane are confronted by Sawyer, but she goes into shock after losing her ultra voice in an explosion. As the building collapses, Dutch and Benny return to port, and Revy, Eda, Jane, and Rock jump onto the boat along with several of the bounty hunters. Dutch begins using evasive maneuvers to cause the bounty hunters to fall off the boat, and Revy dispatches the remaining bounty hunters except Russel, who manages to make it to the engine room, where he is confronted by Eda. Russel realizes that he saw Eda in Washington, D.C., and Eda reveals that she is a CIA agent before killing him. In the computer room, Benny manages to access Jane's counterfeiting files using his hacking talents, and Jane kisses him in return. Shenhua and Lotton the Wizard are shown to have survived, with Lotton revealing that he wears a bulletproof vest. He offers to help Shenhua reach medical help for her gunshot wound and notes that Sawyer had also survived the collapse. He states that they should take her with them as well.

Rock and Revy join Balalaika on a trip to Japan, where she agrees to take sides in a feud between warring yakuza clans.

Balalaika continues making waves in the Japanese underworld. Meanwhile, Rock has another encounter with Yukio - and learns that she is heavily involved with one of the clashing yakuza families.

Balalaika reminisces on her past, recalling that she intended to enter the Olympic rifle shooting event in Moscow 1980 to restore the reputation of her father, and found herself at the front lines in the Soviet war in Afghanistan. Following the war, she and the soldiers formerly under her command joined the Russian Mafia. Yukio severs her ties with her former life by staying late at school with her friend Maki, then being picked up by her henchmen despite Maki's pleas. the new head of the Washimine Group, Yukio orders a counterattack at Hotel Moscow, and Ginji leads the attack. Revy, after picking up a package from Benny with her pistol, goes with Rock to speak with Yukio about withdrawing from the conflict. When Yukio returns home, she is kidnapped by Chaka and his men before Rock arrives. Ginji arrives at the house and Rock convinces him to let Revy aid him in recovering Yukio. When Ginji asks why Rock is aiding him, Rock responds that he cannot accept the notion that Yukio would throw away a normal life for that of the criminal underworld, which Ginji agrees with.

Revy and Ginji unleash on Chaka with brutal force, allowing Rock to grab Yukio and escape. The next day, Balalaika begins the next stage of her plan to violently eliminate the Washimine Group.

Yukio takes action to stop the systematic destruction of the Washimine Group. Later, after Rock confronts Balalaika about her ruthless campaign of violence against Yukio, he suddenly finds himself at gunpoint.

The body count rises as Rock takes desperate measures to force Yukio into giving up on crime. But with so much blood already spilled, it might be too late for her to return to a peaceful, normal life.