Mientras que en un viaje de negocios en el mar para su compañía, Rokuro Okajima es secuestrado por los miembros de la Compañia del Lagoon: Dutch, Revy, y Benny. Después de obtener un disco confidencial para su cliente, Balalaika, el jefe del Hotel Moscú y de una parte de la mafia rusa, Revy toma Rokuro como un rehén en su nave, El Black Lagoon, para pedir un rescate. A pesar de esto, Rokuro comienza a vincularse con los miembros de la Compañía del Lagoon, y Dutch le da el apodo de "Rock". Mientras tanto, el consejo de la compañía de Rock le da a Kageyama, el superior de Rock, la autoridad para perseguir el disco desaparecido, y Kageyama contrata a un grupo mercenario para atacar a la Compañía del Lagoon cuando se detienen en la ciudad portuaria de Roanapur. El grupo despacha a la mayoría de los mercenarios y se escapan hacia el Black Lagoon en su vehiculo. Sin embargo, Kageyama se comunica con la compañía del Lagoon, que informa a Rock que ha sido declarado muerto por la compañía y poco después un helicóptero muy armado del mismo grupo de mercenarios comienzam a perseguir el Black Lagoon.

Para evadir al helicoptero, Dutch conduce el Black Lagoon por un río, pero llega a un callejón sin salida. Al darse cuenta de la inutilidad de su situación, los miembros del Lagoon comienzan a planear lo peor. A pesar de esto, Rock crea un plan para derrotar al helicoptero, deduciendo que la mentalidad del piloto es similar a la de un duelista, que quiere enfrentarse a su oponente cara a cara. Siguiendo el plan de Rock, Dutch utiliza un barco hundido como trampolín para lanzar el Black Lagoon al aire y destruir al helicoptero con torpedos. La Compañía del Lagoon logra entregar el disco a Balalaika, que le da el disco a Kageyama, ya que había hecho un trato con la mafia rusa como una contingencia. En lugar de regresar con Kageyama, Rock decide quedarse con la Compañía del Lagoon, que lo aceptan como un nuevo miembro.

Durante su estancia en Roanapur, donde se encuentra la compañia Lagoon, Dutch es abordado por Chin, un gángster que advierte a Dutch de los riesgos de continuar trabajando para Balalaika. Dutch ignora sus advertencias y recibe un trabajo de un patrón anónimo. Mientras el grupo deja el Black Lagoon, Chin contacta a Luak, el jefe de una pandilla de piratas, para matar a la compañía Lagoon, y Luak ataca al Black Lagoon con un escuadrón de barcos. Dutch engaña a dos de los barcos para que se destruyan entre ellos a través de fuego amistoso, y Revy destruye el resto con un lanzagranadas M79 y un PM-63 RAK mientras saltan de un barco a otro. Posteriormente, se descubre que el trabajo es un engaño creado por Chin, que es asesinado por Balalaika.

La tripulacion del Lagoon es enviada a recuperar una pintura, "Los Doce Caballeros Led de Brunhilda", de un barco hundido en la Segunda Guerra Mundial que salió de Alemania durante la derrota de Alemania nazi y fue hundido por la marina de guerra de Estados Unidos cerca de Yakarta. Dutch compra equipo de buceo para Rock y Revy para utilizar en la recuperación de la pintura, y Benny instruye a los dos a entrar en el submarino a través de sus tubos de torpedo y crear un agujero para salir. Después de Rock y Revy, con un fusil de asalto submarino APS, comienzan a descender, el Black Lagoon es atacado por un grupo de neonazis que disparan misiles TOW a la nave.

El Black Lagoon evade los misiles TOW, pero Dutch y Benny observan que los nazis envían un equipo bajo el agua para recuperar la pintura. Dentro del submarino, Rock y Revy localizan la pintura, pero Revy insiste en buscar en la nave medallas y otros objetos de valor. Cuando Rock expresa su rechazo, Revy afirma que su turbulenta niñez la empujó a rechazar a Dios, el amor y otras emociones y creer que lo unico que tiene valor es el dinero. Los dos son atacados por los nazis y en medio del tiroteo, Rock pierde la pintura. Los nazis la obtienen y se retiran de nuevo a la superficie con ella. Revy intenta perseguirlos, pero Rock la obliga a abandonar la lucha cuando los nazis usan ametralladoras para disparar al agua. Rock y Revy regresan al Black Lagoon, donde Dutch planea un asalto a la nave de los nazis para recuperar la pintura.

Dutch y Revy abandonan el Black Lagoon en una lancha para atacar la nave de los nazis. Con los nazis celebrando su recuperación de la pintura, los dos entran fácilmente en la nave, y Dutch instruye a Revy para distraer a la tripulación mientras que él busca la pintura. Revy obliga, matando a todos los nazis que se encuentra, pero Dutch se ve obligado a detenerla cuando intenta matar a los miembros de la tripulación civil, lo que Dutch atribuye a la inquietud de Revy en aceptar Rock en la tripulación. Dutch finalmente encuentra a Ratchman, el comandante nazi, hablando con Sir Alfred, un ex miembro de Schutzstaffel que ordenó a Ratchman recuperar la pintura. Dutch deduce que Alfred contrató a la Compañía Lagoon para asegurarse doblemente que adquiriría la pintura, y Ratchman está furioso con esta revelación. Después de que Alfred termina la conversación, Dutch y Revy matan a Ratchman, terminando su misión.

Dutch envia a Rock y Revy a hacer recados por todo Roanapur, y Revy está disgustada de que se vea obligada a realizarlos con Rock. Cuando se detienen en "La Iglesia de la Violencia", una organización que se presenta como misioneros religiosos con el fin de traficar drogas y armas ilegales, Rock se las arregla para utilizar su inteligencia empresarial para reparar un acuerdo con Yolanda (la jefa de esta organización), después de que Revy le apunte con una pistola. Yolanda está impresionada por la habilidad de Rock y le pide a Revy que lo imite. Después, Rock y Revy comienzan una pelea en un restaurante, ya que Rock está furioso con Revy por comenzar a actuar como sus anteriores superiores en Japón, dejando a Revy sin palabras. Watsap, el jefe de la policía corrupta de Roanapur, los regaña por causar un alboroto y se los lleva. Se reconcilian en el asiento trasero de un coche de policía.

La tripulación del Lagoon es contratada por un cártel colombiano para entregar un rehén, y Dutch asigna a Rock vigilar al chico mientras están de camino. Rock se entera de que el muchacho es García Lovelace, el heredero de una de las familias más ricas de Sudamérica, y que el cártel había secuestrado a García después de que su padre se negara a permitir que el cártel lo intimidara. Preocupado por las circunstancias que rodearon el secuestro de García, Dutch contacta a Balalaika para obtener información sobre la familia Lovelace y el cártel. Al entrar en Roanapur, García confía en que Roberta, la criada de la familia Lovelace, lo salvará. Mientras tanto, Roberta viaja a través de Roanapur en busca de García, y se enfrenta a miembros del cartel en un bar. Mientras la tripulación del Lagoon y García entran en el mismo bar, Roberta comienza un tiroteo con los miembros del cártel.

Roberta despacha a la mayoría de los miembros del cártel, y García se sorprende de su capacidad de combate. Revy revela la presencia de los miembros del Lagoon durante el tiroteo, y se queda inconsciente cuando Roberta le dispara un proyectil de 40 mm. García le pide a los miembros del Lagoon que lo lleven con ellos, y logra escapar. Uno de los miembros del cártel identifica a Roberta como una ex guerrilla de las FARC con una gran recompensa por su cabeza. Roberta destruye la barra con las granadas y roba un coche para perseguir la compañía de la laguna. Habiendo determinado la identidad de Roberta, Balalaika moviliza a los soldados para ayudar a los miebros del Lagoon. Cuando Roberta alcanza a la tripulacion del Lagoon, Dutch consigue destruir el motor de su coche antes de ser sacado casi de su coche por ella, y Benny comienza a conducir en callejones y calles laterales. Cuando vuelven a la carretera principal, aparece Roberta de nuevo con otro coche que engancha en la parte posterior de su coche.

La tripulacion del Lagoon es contactada por el Sr. Chang (jefe de la Tríada Roanapur), para transportar a la CIA un maletín que contiene información sobre los Protectores del Frente Islámico, un grupo terrorista. Mientras charlan, son atacados por los terroristas, pero Chang y Revy despachan a los atacantes. El grupo sale en el Black Lagoon, pero son perseguidos por barcos pertenecientes a los terroristas debido a la previsión de Masahiro Takenaka, uno de los líderes de los Protectores del Frente Islámico. Revy y Rock se ven obligados a abandonar el Black Lagoon y buscar una ruta terrestre. Takenaka se presenta con un vehiculo para rescatarlos y aunque Revy ve su farsa, se lleva a Rock y escapa. Revy es salvada por Shenhua, un asesino en el empleo de Chang, y ella convence Shenhua y su compañero Leigharch para salvar a Rock para recuperar los documentos.

Takenaka comienza a interrogar a Rock, revelando que es un ex miembro del Ejército Rojo Japonés. Cuando Rock le pregunta por qué sigue luchando por una causa perdida, comenta que lucha por dar sentido a los sacrificios que hizo en el pasado por sus creencias. Debido al método jovial de Takenaka de conducir el interrogatorio, Ibraha, el camarada de Takenaka, le pregunta a Takenaka si puede torturar a Rock, pero Takenaka se niega. Revy y Shenhua allanan el campamento, escapan con Rock, y son seguidos por una flota de vehículos bajo el mando de Ibraha. Revy y Shenhua se encargan de la mayoría de los vehículos, e Ibraha ordena al resto de sus hombres que continúen la persecución. Cuando Ibraha se niega a dar la orden de retirada, Takenaka le dispara y le da la orden. Revy entrega los documentos a los agentes de la CIA y le recrimina que no se deje volver a capturar.

Chang organiza una reunión entre los principales señores del crimen de Roanapur: él, Balalaika, Abrego, un jefe del cartel colombiano, y Verrocchio (líder de la rama Roanapur de la mafia italiana). Balalaika rechaza los intentos de Chang de fomentar la cooperación, e insiste en que Hotel Moscú va a encontrar y eliminar a los asesinos. A la mañana siguiente, dos de los subordinados de Balalaika son asesinados, y Watsap revela que los asesinos son un par de niños gemelos. Una gran recompensa se coloca por los gemelos, y la ciudad a llenarse de cazarrecompensas, Eda, un miembro de la Iglesia de la Violencia, sugiere a Revy que se unan a la caza también. En el escondite de los gemelos, sus patrocinadores están disgustados al descubrir que los gemelos están brutalmente torturando a uno de los subalternos de Balalaika. Mientras tanto, Balalaika pide a Rock información acerca de los gemelos.

Rock determina que los gemelos son de Rumania, y Balalaika le pregunta a Rowan (dueño de un club de striptease), por todas las películas porno rumanas que tiene. En una reunión con Chang, le revela que encontró a los gemelos en una de las películas, en la que se llamaban Hansel y Gretel, y menciona que muchos huérfanos del régimen de Nicolae Ceauşescu fueron vendidos en el mercado negro y forzados a participar en peliculas porno. Después de examinar algunos documentos que le entrega, Chang acuerda formar una alianza con Balalaika para eliminar a los gemelos, y Balalaika moviliza a Visotoniki, el antiguo grupo de soldados que lucharon con ella en Afganistán. Los gemelos llegan a la sede de Verrocchio, lo matan e intercambian el fuego con Chang cuando salen. Para distraer a los cazadores de recompensas, usan un coche como señuelo, pero se enfrentan a los Visotoniki y al final son acorralados por Eda y Revy.

Eda y Revy comienzan un tiroteo con los gemelos, pero los Visotoniki llegan, poniendo fin a su lucha. Hansel y Gretel deciden separarse y Revy vuelve a casa. Gretel esquiva a Eda, y mientras la sostiene como un rehén, pide que ella encuentre un barco de la partida para ella y su hermano. Mientras tanto, los Visotoniki contratan a Hansel ya pesar de sus mejores esfuerzos, no sufren bajas mientras lo atacan durante toda una noche. Hansel eventualmente encuentra a Balalaika en un parque, pero es atrapado por sus hombres. En otra parte, Gretel contrata a la tripulacion del Lagoon para llevarla, y habla con Rock de su pasado, sobre todo lo que ella tuvo que aguantar debido al régimen de Ceauşescu y a los mercaderes de personas. Cuando el Black Lagoon alcanza el punto de partida, Gretel es asesinada por alguien del Hotel Moscú, pero Rock señala que murió pacíficamente mirando al cielo.

Dollar Jane, una falsificadora de dinero que trabaja para un sindicato del crimen de Florida, enfurece a sus jefes al romper un plazo y huir por ello. Pide refugio en la Iglesia de la Violencia, donde Eda y Revy están bebiendo, ella es rechazada por Eda. Los miembros de la mafia de Florida llegan momentos después e incendian la Iglesia, lo que hace que Eda y Revy respondan. A ellas se unen Rico (un aprendiz de sacerdote) y Yolanda, y expulsan a los miembros de la mafia. Dentro de la Iglesia, Jane demuestra su habilidad para la falsificación, y Eda la envía a un motel. Russel, un miembro de la mafia de Florida, comienza a buscar cazarrecompensas en Roanapur, incluyendo a Shenhua y Sawyer (El Limpiador), un mudo que usa una motosierra en batalla. A pesar de su disposición a obtener la recompensa, los cazarrecompensas critican a Russel por su inexperiencia en la ciudad y su apariencia de vaquero. Cuando los cazarrecompensas se van, Rock, Eda y Revy llegan al motel de Jane.

Los cazarrecompensas llegan al motel de Jane, y ella se escapa gracias a los preparativos que Eda había hecho de antemano. Jane ve a Eda y acepta pagar cualquier precio si Eda la salva. Eda y Revy obligan a los cazarrecompensas a retirarse, y luego se dirigen al muelle del Lagoon. Cuando Russel llega a la escena, Shenhua exige más dinero, ya que Eda y Revy están involucradas. El plan de Eda para escapar en el Black Lagoon está descartado debido a que Dutch y Benny se lo llevaron para un trabajo, y se ven obligados a esperar en la casa del muelle, donde son rodeados y atacados por los cazadores de recompensas. Cuando Shenhua y Sawyer llegan, Revy maldice su desgracia, y Rock y Jane se ven obligados a ir al techo cuando el edificio se incendia. Mientras tanto, Dutch comienza a acelerar de vuelta al puerto y Revy establece una trampa para Shenhua.

Shenhua evade la trampa, pero es fusilado por Eda después de que Revy actúe como señuelo. En el tejado, Rock y Jane son atacados por Sawyer, pero ella entra en shock después de perder su electrolaringe en una explosión. Lotton el Mago se enfrenta a Revy, quien le dispara. A medida que el edificio colapsa, Dutch y Benny regresan al puerto, y Revy, Eda, Jane y Rock saltan al barco junto con varios de los cazadores de recompensas. Dutch comienza a emplear maniobras evasivas para hacer que los cazadores de recompensas caigan del barco, y Revy despacha a los cazadores de recompensas restantes excepto Russel, que consigue llegar a la sala de máquinas, donde se enfrenta a Eda. Russel recuerda haber visto a Eda en Washington, DC, y Eda admite ser agente de la CIA antes de matarlo. En la sala de ordenadores, Benny logra acceder a los archivos de falsificación de Jane usando sus habilidades de hacker, y Jane le da un beso a cambio. De regreso al muelle, Lotton el Asistente, que sobrevivió gracias a su chaleco antibalas, se ofrece a ayudar a Shenhua a llevarla a un médico por su herida de bala.

Rock es contratado por Balalaika para ser su traductor en un viaje a Japón, y Revy lo acompaña. Balalaika negocia con el Grupo Washimine, un grupo yakuza caído en tiempos difíciles, y se compromete a destruir el Consejo Kosa, otro grupo yakuza, debido a un trato del Grupo Washimine. Tras la conclusión de su acuerdo, Balalaika ordena una explosión en una base del Consejo de Kosa. Después, Revy y Rock van a un festival japonés, pero Revy causa una escena cuando pierde en un juego de disparos. Ella es detenida por Ginji Matsuzaki, uno de los organizadores del festival, y el compañero de Ginji les impide iniciar una pelea. Ella y Rock intercambian bromas, y cuando ella se va, ella le dice a Rock que su nombre es Yukio. Al día siguiente, Tsugio Bando, jefe del Grupo Washimine, le pide ayuda a Ginji, recordando que Ginji era temido entre todos los yakuza por su uso de una katana en la batalla. Ginji se niega, citando la falta de justicia en los métodos de Bando. Mientras tanto, Rock visita la casa de sus padres, y Revy se entretiene jugando pistoleros con un grupo de niño

Debido a la brutalidad de los ataques de Balalaika al Consejo de Kosa, Bando organiza otra reunión con ella, pero se dan que cuenta que ejecutará sus planes como mejor le parezca. Después de la reunión, Rock es golpeado por Chaka, un miembro del grupo Washimine, y Revy promete matarlo. Después de pedirle a Benny que envíe a Revy sus pistolas, Rock conoce a Yukio nuevamente. Los dos discuten la capacidad de cada uno para elegir su camino en la vida, y Yukio cita a Jean-Paul Sartre. Cuando se va, le dice a Rock que su apellido es Washimine, y Rock se da cuenta de que es parte del Grupo Washimine. En su casa, Bando y Ginji discuten sobre el futuro del Grupo Washimine, señalando que sólo un descendiente directo del jefe anterior puede reclamar su posición. Al día siguiente, Bando intenta asesinar a Balalaika, pero falla y Balalaika lo mata. Después de escuchar esto, Yukio, como la nieta del líder anterior, acepta convertirse en el líder del Grupo Washimine y Ginji jura su lealtad a ella.

Balalaika recuerda su pasado. Ella recuerda que tuvo la intención de participar en el tiroteo olímpico para restablecer la reputación de su padre, pero se encontró en primera línea en la guerra soviética en Afganistán y después de la guerra, ella y los soldados que anteriormente estaban bajo su mando se unieron a la Mafia rusa. Yukio rompe sus lazos con su vida anterior al quedarse hasta tarde en la escuela con su amiga Maki y ser recogida por sus secuaces, a pesar de las súplicas de Maki. El nuevo jefe del Grupo Washimine, Yukio ordena un contraataque en el Hotel Moscú, que es dirigido por Ginji. Revy, después de recoger un paquete de Benny con sus pistolas, acompaña a Rock para hablar con Yukio sobre la retirada del conflicto. Cuando Yukio vuelve a casa, es secuestrada por Chaka y sus hombres. Ginji llega a la casa poco después de Rock, quien le convence de dejar que Revy lo ayude a recuperar a Yukio. Cuando Ginji le pregunta por qué Rock le está ayudando, Rock responde que no puede soportar la decisión de Yukio de tirar una vida normal por la del submundo criminal.

Revy y Ginji llegan a una bolera donde Chaka retiene a Yukio, y despachan a sus hombres. Chaka intenta salir con Yukio, pero Rock toma Yukio y escapa. Chaka entonces encuentra a Revy en un pasillo y cuando él intenta comenzar un duelo con ella, ella lo conduce a Ginji. Chaka intenta disparar a Ginji, pero corta la bala en dos con su katana. A continuación, elimina los brazos de Chaka con su katana y lo ahoga en la piscina adyacente. En otro lugar, Yukio critica a Rock por intentar salvarla de caer en el inframundo criminal, ya que cree que él existe en un "crepúsculo" entre su vieja vida en Japón y su vida criminal en Roanapur, y no está dispuesto a dejar ir cualquiera de ellos. Al día siguiente, Balalaika comienza sus planes para la destrucción del Grupo Washimine.

Los ataques de Balalaika reducen a los miembros del Grupo Washimine a un tercio de su fuerza anterior, y Yukio ordena a los miembros del Grupo Washimine abandonar sus fortalezas para evitar los ataques. Descubriendo que el Hotel Moscú utiliza furgonetas eléctricas para ejecutar sus ataques, Yukio y Ginji utilizan una furgoneta similar para robar un banco para dirigir a la policía hacia las furgonetas del Hotel Moscú. Después del robo, Yukio reflexiona acerca de viajar a Roanapur con Ginji para iniciar un grupo yakuza allí. Revy y Rock se encuentran con Balalaika, y Rock le pide a Balalaika que ponga fin al ataque contra el Grupo Washimine. Balalaika responde manteniendo Rock a punta de pistola, pero libera Rock después de que él dice que es un villano como ella. En un parque cerca de la casa de sus padres, Rock admite a Revy que regresó a Japón para romper sus lazos con su vida anterior, y que ha encontrado la determinación de hacerlo.

Rock se une a Balalaika para sus conversaciones con el Consejo de Kosa, y le pide que destruya por completo al Grupo Washimine para obligar a Yukio a adoptar una vida normal. Balalaika entonces mata al líder del Consejo de Kosa, e informa a Rock que los ataques de Moscú de Moscú al Grupo de Washimine cesarán. Rock sale con Revy en una motocicleta. Son atropellados por una furgoneta conducida por Yukio y Ginji, que secuestran a Rock y le hacen llevarlos a la base del Hotel Moscú. Revy roba un camión y obliga a Yukio a parar la furgoneta. Ginji y Revy luchan mientras que Rock intenta razonar con Yukio. Él deduce que Yukio se sintió obligado a convertirse en parte del inframundo criminal, y admite que deseaba que su vida normal pudiera continuar. Esta admisión hace que Ginji se detenga momentáneamente, permitiendo que Revy le dispare fatalmente. Debido a las muertes por las que se siente responsable, Yukio se disculpa con Rock y se suicida usando la katana de Ginji. Cuando Rock regresa a Roanapur, Balalaika le envía una foto de Yukio, y Rock comenta que quiere ver a Roanapur del "crepúsculo" en el que se encuentra.