Billion, uma cidade que é governada por um homem sinistro chamado Harry MacDowell e sua organização, Millennion, tornou-se o único lugar seguro para uma garota fugitiva chamada Mika Asagi, que fica sob a proteção de um morto-vivo chamado "Beyond The Grave". Grave, retornando dos mortos sem memória, vagueia em busca de seu passado, e depois de derrotar alguns dos melhores soldados da Millennion, que lança uma caçada humana em Grave, com Harry sofrendo um ressentimento incalculável por Grave.

Anos atrás, havia dois jovens que faziam parte de uma quadrilha de rua de quatro homens, Brandon Heat e seu melhor amigo Harry MacDowell. Isso conta a história de suas vidas passadas, começando com Brandon e Harry, junto com os amigos Kenny, Jolice e Nathan, sobrevivendo no bairro controlado por gangues. Durante esse tempo, Brandon desenvolve uma queda por uma garota chamada Maria, mas ganha a indignação de seu tio, Jester, que tem um passado sombrio. Depois de derrotar um líder de gangue chamado Deed em uma briga, eles logo atraem a atenção de um executor da máfia e do irmão mais velho de Deed chamado "Mad Dog" Ladd, que rapidamente mata Jolice e os força a se esconder.

Em fuga como fugitivos de um inimigo desconhecido, Brandon e Harry tentam desesperadamente manter sua gangue unida enquanto a morte de Jolice pesa sobre todos eles. Quando Harry tenta ir buscar ajuda, ele é traído por um corretor de informações desprezível e retorna de mãos vazias e feridos. Brandon se vira para Jester, que exige que ele deixe a cidade com sua vida por causa de Maria e depois salve Brandon dos homens de Deed, antes de ser morto por Ladd. Harry e seus amigos chegam para ajudar, mas todos são mortos, exceto Brandon e Harry no final, antes que um homem da Millennion, Bear Walken, chegue e os salve, matando Ladd. Brandon e Harry se vingam de Deed, matando-o com a pistola Bear deixada para trás.

Harry e Brandon tornam-se temidos após a ação, com Harry fazendo uma jogada ousada humilhando o chefe do crime do bairro. Harry decide agir de acordo com seus sonhos de liberdade depois que enterram Nathan e Kenny, e Brandon se junta a ele. Ao mesmo tempo, Maria é abordada por Asagi Caldwell, líder da Millennion e amiga de Jester, que lhe oferece uma nova vida e proteção em sua mansão. Enquanto Maria sai, Brandon e Harry estão sendo atacados por bandidos, mas Asagi envia guardas e seu executor, Randy, para resgatar Brandon e Harry a pedido de Maria. Aprendendo que eles são da Millennion, Harry implora a Randy para deixá-lo se juntar à Millennion, e Brandon novamente segue a decisão de Harry, admitindo que ele espera encontrar Maria e Harry viajando para a organização.

Na porta da Millennion, Harry e Brandon se separam. Enquanto Brandon trabalha como cobrador de dívidas da máfia, gradualmente se acostumando à linha de trabalho e mudando consideravelmente ao testemunhar a morte em primeira mão, conquistando o respeito de seus colegas de trabalho. Ele se reúne com Harry depois de um trabalho e os dois discutem como estão indo suas vidas, e Brandon é apresentado a Balladbird Lee e Bob Poundmax pela primeira vez. Mais tarde, Harry dá a Brandon o endereço da escola em que Maria estuda e os dois se reencontram pela primeira vez em meses.

Maria, que acreditava que Brandon havia morrido, está feliz em se reunir com ele também. Mas Brandon recebe um aviso para não ver Maria novamente dos chefes da organização, para que sua própria vida não seja tirada, o que Harry ri ao pensar que Brandon não teria ido tão longe. O líder da Millennion, Big Daddy, convoca Brandon para sua mansão, onde os dois discutem a situação de Maria e Asagi recebe Brandon para visitar Maria, mas apenas em sua mansão. Brandon é convidado para uma festa que Big Daddy está organizando onde sua conexão com Maria cresce, mas o romance é perturbado pelos eventos que ocorrem naquela noite. Harry, obcecado em ganhar poder ao se tornar um membro da "Família", o pináculo da Millennion que fica próximo ao Big Daddy, impede uma tentativa de assassinato por um grupo rival, enquanto Brandon salva o Big Daddy, mas em contrapartida, leva um tiro no peito.

Em um período de cinco anos, Brandon agora é um dos melhores varredores da Millennion, um assassino com habilidade inacreditável e uma forte amizade com Harry, que subiu na hierarquia e também através de decisões comerciais inteligentes e capitalização das habilidades de Brandon. Criando sua própria equipe de crack com Bob, Brandon e Lee, Harry tem subido estrategicamente sua escada. Um golpe é aplicado em Harry devido à sua incrível influência e o assassino "Madman" Bunji Kugashira é introduzido, tentando matar Harry. Harry, no entanto, revela o engano das pessoas que contrataram Bunji, e um confronto de três vias começa quando o engano é revelado e um grande tiroteio começa, com Brandon entrando na briga graças a uma ligação frenética de Bob. Bunji se recusa a trabalhar para a Millennion, a menos que seja derrotado em uma briga, e Brandon alegremente se prepara para o desafio. No final, Bunji é visto trabalhando como varredor e se torna aprendiz de Brandon, leal a ele, à organização e a Harry.

Um homem chamado Brad Wong é libertado da prisão e se reúne com um velho camarada de guerra, Cannon Vulcan, líder de Lightning. Vulcan tropeçou em algo grande, um projeto secreto que criará super soldados invencíveis dentre os mortos chamados "Necro-Rise". Com esse conhecimento, ambos acreditando que serão capazes de atingir seus próprios objetivos, Wong procura ter um campo de batalha definitivo e procura remover todos os seus laços anteriores, deixando seu ex-sindicato, Vulcano, e obtendo a confiança de seus próprios subordinados. Enquanto os dois discutem seus planos em um bar isolado, Wong e Vulcan encontram Harry MacDowell pela primeira vez, que se interessou pelas atividades mais recentes de Lightning e cético em relação a seus motivos a mando de Big Daddy, que recebeu a palavra do líder do Vulcano sobre o lançamento de Wong. Wong, que tem o título de "Guerra do Sangue" por transformar tudo em um campo de batalha, está prestes a atirar em Harry em fúria bêbada antes de conhecer Brandon Heat, que já tinha Wong à mão armada sem sua consciência. Espantado com a eficiência desses novos inimigos, Wong "prepara" seus subordinados para se tornar o exército de mortos-vivos de Vulcano.

Com as peças no lugar e suas forças reunidas, Millennion e Lightning estão prontos para a guerra entre si, com Brandon, Harry, Bunji e Wong no centro. Wong encontra Brandon e Bunji na rua e detona várias bombas que colocam a cidade em pânico, e o "Exército de Homens Mortos" da Vulcan começa a invadir as fortalezas, incapazes de serem mortas e varrer o maior número de milhões de dólares junto com vários executivos. Harry tenta freneticamente avisar a todos, mas percebe que a única maneira que Lightning poderia ganhar tanto terreno era se um traidor de dentro da Millennion estivesse lhes fornecendo informações. Wong e seus soldados conseguem confrontar e "capturar" Brandon e Bunji, e Brandon tenta interrogar o objetivo de Lightning. Guerra do Sangue afirma que eles querem o Big Daddy, e Brandon concorda em encontrá-lo dentro de um armazém. Harry assume total responsabilidade pela situação e descobre que Lee, que é parente de Cannon Vulcan por sangue, é de fato o traidor, e o desafia para um duelo, enquanto Brandon chega ao esconderijo de Wong e se prepara para enfrentar a Guerra do Sangue e seu exército de mortos-vivos sozinho.

A guerra começou quando Harry se defronta com Lee, que implementa extenso treinamento nas táticas de sombra e furtividade, e Brandon luta contra uma multidão de soldados mortos-vivos quase invulneráveis. Como seus acertos se mostram ineficazes, Brandon passa a usar as rodadas de D-Point que ele pegou mais cedo e começa a espantar os Deadmen, embora ele ainda não consiga mantê-los baixos. Bunji vem em auxílio de Brandon, mas é inútil, pois ambos estão feridos. Depois de sofrer danos maciços de Lee, Harry começa a deduzir os motivos de Lee e convence Lee a acreditar temporariamente em sua causa e procurar poder e liberdade. Lee se torna o primeiro de muitos familiares "transformados" de Harry, e juntos os dois extraem o segredo de Lightning e matam Cannon Vulcan, enquanto Brandon e Bunji estão em sua última perna. Wong promete revivê-los para que eles possam servir sob ele, mas logo os soldados Necro-Rised começam a se desintegrar devido ao prazo esperado do experimento. Wong é ferido por Brandon e se retira, e ele e Vulcan passam seus últimos momentos relembrando sua história. Quando Vulcano morre, um Wong moribundo engole uma fórmula Necro-Rise e se transforma em um monstro na frente de Brandon e Bunji.

Três anos se passaram desde que Brandon viu Maria pela última vez, e ele vive uma vida fria e apática desde então, lamentando sua profissão de assassino e, ao mesmo tempo, lutando entre sua lealdade a seus amigos, Maria e Harry e a Millennion e Big Daddy. Brandon iniciou seu próprio grupo, True Grave, que se tornou mais ou menos tão habilidoso quanto o Overkills do Bear Walken. Harry e Sherry sentimentalizaram seu relacionamento, contra os desejos de Bear. Harry começa a fazer contato ilegítimo com o cientista Necro-Rise, Dr. Tokioka, e Maria revela que sabe a verdade por trás da morte de Jester, da vida de Brandon e da organização do Big Daddy.

Big Daddy tricks Brandon into visiting Maria before dropping a bombshell on his number one killer. Harry frames an innocent man to protect his interests in a very secret project.

Harry e Brandon decidem chegar ao topo, Brandon por convicção e Harry por engano, mas a amizade deles está lentamente se desfazendo conforme promessas antigas e memórias antigas começam a desaparecer da mente de Harry. O Big Daddy reúne toda a Família Millennion para anunciar o próximo líder, Arzac Tino, quando todos acreditavam que obviamente seria Harry, que havia assumido o controle de mais de oitenta por cento do Millennion naquele momento. Eles revisitam a cidade em que cresceram juntos, vendo um antigo orfanato onde se conheceram quando crianças, depois voltando ao bar onde viviam e depois aos túmulos de Nathan, Kenny e Jolice, todos os que Harry esqueceu. Harry revela que Arzac sofreu um ataque cardíaco e foi hospitalizado quando eles retornam ao prédio da Millennion e começam a subir no elevador, Brandon fica na luz, enquanto Harry fica no escuro. Silenciosamente, Harry sugere que eles matem o Big Daddy e tomem posse para que Brandon possa ter Maria sozinha, mas Brandon responde dando um soco nele e segura uma arma enquanto Harry revela sua natureza traidora. Harry, já amargo por ouvir Brandon permanecer leal ao sindicato, e não a seu melhor amigo, atira furiosamente em Brandon várias vezes e depois pelo olho esquerdo, empurrando seu melhor amigo para fora do elevador e até a morte.

A morte de Brandon enviou ondas de choque ao longo da Millennium. Harry agora chegou ao topo da organização e convence qualquer potencial causador de problemas a permanecer leal. Bunji não está preocupado com o fato de seu mentor ter sido morto e se apegar fiel ao Código de Ferro, renomeando o True Grave como The Kugashira Group. Big Daddy acredita que Harry manterá a harmonia dentro da organização e revela que Maria está grávida de seu filho. Bear Walken decide ficar por perto para proteger Harry e cuidar de Sherry. Enquanto visitava o túmulo de Brandon, Maria esbarra nos antigos colegas de Brandon, Widge e Gary, que acidentalmente deixaram escapar que ela havia sido assassinada por trair a organização. Big Daddy relutantemente informa que Harry foi quem o matou. O Dr. Tokioka concluiu o projeto Necro-Rise e, a caminho da startup, Harry mata um dono de loja e tem um colapso devido à culpa de matar seu melhor amigo. Ele é interrompido quando as notícias de que a startup Necro-Rise deu errado e que monstros estão destruindo a instalação. Enquanto Tokioka escapa, Necro-Risen Brandon é visto destruindo vários monstros que estão à solta.

Enquanto Harry, Bob e Lee examinam as ruínas da instalação, eles encontram um membro de P&D, Laguna Glock, que lhes diz que o projeto Necro-Rise funciona ainda melhor em assuntos ao vivo e se oferece para continuar a formar um exército para Millennium, o que Harry aceita. O Dr. Tokioka entrega uma carta de Brandon ao Big Daddy, na qual Brandon confessa que sabia tudo o que Harry estava fazendo, mas pensava que na época era para o bem da organização. Ele também se encontrou com o Dr. Tokioka e pediu que ele o revivesse caso algo acontecesse se Harry se desviasse da pista, indicando que sabia que algo teria acontecido. Big Daddy impede Maria de confrontar Harry e diz a ela que Brandon ainda está vivo e lhe dá um caso para lhe dar se ela precisar de ajuda dele. Ele a coloca em um lugar mais seguro e confronta o próprio Harry. Ele diz a Harry que Brandon sabia de tudo, e um visivelmente chateado Harry mata Big Daddy em um acesso de raiva, indicando que ele está lentamente perdendo a cabeça. Harry promete matar qualquer um e qualquer coisa que possa lembrá-lo do Big Daddy.

Treze anos depois, o governador do estado é assassinado por um novo tipo de Necro-Rise, chamado Orgman, que é muito mais forte e pode se amedrontar à qualquer um, a Millennion agora exporta esses orcmen para lucros enormes. Laguna Glock tem a tarefa de aumentar a produção de Bear Walken, que está revoltado com o recém-desenvolvido projeto Necro-Rise, mas só fica na Millennium para cuidar de sua filha. É revelado que Balladbird Lee e Bob foram submetidos ao procedimento de "Superiorização" para fazer orcmens com conscientes. Maria foi encontrada e tem uma filha chamada Mika Asagi. "Sangrento" Harry, como é agora conhecido, ordena que eles sejam mortos, a fim de evitar disputas por sucessão. Mika consegue escapar do esquadrão da morte, mas Maria é morta e Butler Tokioka é morto por um Orgman. Mika chega ao Dr. Tokioka depois de conhecer o passado de sua mãe. Enquanto vão embora, eles são atacados por um grupo de orcmen e Beyond The Grave desperta, o que remete à cena de abertura do primeiro episódio.

Grave mata o orcmen atacando o caminhão. Ao passar a ruína de um bar por Jolice, algumas lembranças confusas voltam para ele. Ele segue com Mika para os túmulos de Kenny, Nathan e Jolice e é atacado por alguns membros da Millennium e alguns orcs. Depois de matá-los, as memórias de um dos orcmen mortos são recuperadas por Bob, que passa as informações para Harry, que percebe que Brandon está de volta. Mais lembranças confusas retornam a Grave e ele determina que estava tentando proteger alguém, mas não consegue descobrir quem. Bunji quer matar Brandon, mas a tarefa vai para Bob, que quer tentar usar suas habilidades superiores recém-adquiridas.

Em um breve flashback, Bob está em coma devido à sua obesidade mórbida e colesterol alto. Laguna Glock sugere a Balladbird Lee que a superiorização pode salvá-lo, mas é um risco. Lee concorda, mas ele próprio é submetido ao procedimento primeiro como sujeito de teste. Mika descobre a história da Millennion e quem é quem na organização. Ela aprende sobre Harry Sangrento e os Quatro Grandes, sendo Bear Walken, Bob Poundmax, Balladbird Lee e Bunji Kugashira. Tendo aprendido sobre uma grande festa na mansão onde todos os grandes chefes estarão presentes, Grave foge para assassiná-los. Em vez disso, ele é recebido por muitos orcmen, uma armadilha orquestrada pela contra-inteligência de Bob, bem como pelos grandes chefes. Os chefes partem, exceto Bob, que fica para trás para testar seus poderes superiores. Enquanto se afastam, Bunji e Bear parecem nostálgicos por terem visto Brandon novamente. Durante a briga com Bob, Grave se lembra de Harry e o que ele fez.

Balladbird Lee fica arrasado após a morte de Bob, seu melhor amigo. Harry descobre que Brandon deve ter tido alguma ajuda para ser Necro-Rised e deduz que o Dr. Tokioka foi quem o ajudou. Grave e Mika visitam a antiga casa de Maria e ele se lembra mais de seu relacionamento anterior com ela antes de ingressar no sindicato. Millennion descobre a localização deles e Bunji entra sozinho para enfrentar Grave, com quem ele se considerava próximo. Apesar de ser humano contra um Necro-Rise, ele veio preparado. Armado com bombas e uma arma protótipo para uso contra os Necro-Rises, ele confronta Grave, exigindo saber por que ele traiu a organização. Grave não responde e quase morre quando Mika o interrompe. Por um senso de honra, mas muito irritado, Bunji não mata Mika, mas a assusta sem sentido, atirando nela. Isso irrita Grave, e antes que as toxinas o paralisem completamente, ele bate violentamente em Bunji.

Bunji está desaparecido após sua derrota nas mãos de Grave e mais tarde é mostrado que ele bebe muito e é um vagabundo. Widge e Gary, que agora não são mais homens do sindicato, recebem uma visita de Grave e Mika. Mika explica a eles o que aconteceu com Brandon e Gary acidentalmente deixa escapar que Big Daddy foi morto. Enquanto isso, o Dr. Tokioka obtém informações sobre tudo que tem a ver com os Necro-Rises e os Superiores, incluindo suas fraquezas. Grave deixa Mika sob os cuidados de Widge e Gary e dirige para um obstáculo onde ele é atacado por orcmen. Balladbird Lee deduz que, já que Grave está sozinho com um carro, ele deve estar recebendo ajuda de mais pessoas e procura Widge e Gary. Widge explica para Mika a história do Big Daddy e as circunstâncias da morte de Brandon e eles são interrompidos por Lee fazendo uma entrada. Usando seus poderes superiores, Widge e Gary são violentamente separados e Mika é levada. Quando Grave retorna à casa deles, ele fica arrasado ao ver o destino de seus velhos amigos. Finalmente Bunji aparece no laboratório de Laguna Glock e oferece seu corpo para ser atualizado.

Balladbird Lee informa Grave onde ele pode encontrar Mika. No entanto, ele também é acompanhado por cento e cinquenta orcmen. Enquanto espera Grave aparecer, Mika aprende sobre seu pai, Big Daddy, com Lee. Grave derrota todos os orcmen e o Dr. Tokioka leva Mika para segurança a bordo de um trem. Lee usa seus poderes Superiores para pegar o trem e os ataca, mas usando as informações que o Dr. Tokioka adquiriu sobre os Necro-Rises e Superiores, ele desenvolveu uma bala anti-Superior para Grave usar. O corpo de Balladbird Lee se desintegra depois que ele é baleado com a nova bala, mas o Dr. Tokioka é mortalmente ferido no processo. Antes de morrer, ele diz a Grave que ele só pode se mover por mais dez dias com o equipamento restante, para que ele tenha que derrotar Millennion nesse período.

Widge e Gary estão enterrados ao lado de Maria, Big Daddy, Dr. Tokioka e Butler Tokioka, ao lado dos túmulos de Kenny, Nathan e Jolice. No caso da morte de Balladbird Lee, Bear Walken havia feito os preparativos para enfrentar o próprio Grave. Vários executivos do sindicato estão discordando da atitude de Harry de lutar contra Grave, preferindo que ele resolva suas diferenças com Brandon para proteger o sindicato. No entanto, Harry prefere lutar e manda um Orgman matar todos aqueles que se opõem a seus pontos de vista. Os Overkills de Bear localizam Grave e Mika, mas seu último pedido para eles é se desfazer. Gratos que Bear os poupou de serem transformados em orcmen, eles respeitam sua última ordem. Bear conversa com Grave e organiza um duelo na mansão onde ninguém do sindicato pode entrar no caminho de Grave. Tendo ouvido o que Bear tinha a dizer, Mika entende por que Bear está com o sindicato e que ele é um homem decente. Na mansão, os preparativos de Bear para o duelo são revelados como sendo sua superiorização, mas Grave usa as balas anti-superiores. Antes de Bear morrer, ele pede desculpas a Grave e pensa em sua filha e no que ele havia feito para cuidar dela, em uma atitude semelhante ao que Brandon havia feito pelo Big Daddy.

A cidade inteira está paralisada devido ao conflito e os Overkills decidiram se tornar os guarda-costas pessoais de Harry. Millennion se dividiu em duas facções: as leais a Harry e as que preferiam Big Daddy, dirigido por Biscoe. A facção de Biscoe faz várias tentativas de assassinar Harry durante o dia, mas nenhuma é bem sucedida, no entanto Sherry é morta em um incêndio cruzado. Apesar de Mika implorar para que Grave pare e vá embora com ela em família, longe de Millennion, Grave vai ao quartel-general para encerrá-lo de uma vez por todas, apenas para encontrar um superior Bunji no saguão deserto. Um violento tiroteio acontece e Bunji é morto, mas não antes de infligir graves danos a Grave, cujo próprio corpo não está mais se recuperando adequadamente. Quando Grave chega ao escritório de Harry, ele o encontra vazio, mas vê algumas fotografias emolduradas, incluindo uma de toda a gangue antiga, com Brandon, Harry, Kenny, Nathan e Jolice.

Grave é visto andando rigidamente e sem rumo. Então a cena muda para Harry. Não tendo mais aliados vivos dentro da Millennion, os dias de Harry estão contados. Todo mundo quer matá-lo e a nova facção adquiriu balas para matar os Orgmen. Harry é o único que assiste ao funeral de Sherry. Mika tenta encontrar Grave na sede, mas apenas encontra o novo chefe de Millnenion, que lhe diz que ela não é mais alvo e é livre. Enquanto se afasta do funeral de Sherry, Harry vê um Orgman ser abatido e ele é forçado a escapar dos capangas do sindicato. Durante sua fuga, ele bate o carro e olha para trás como sua queda aconteceu. Ele então tem um flashback nostálgico, onde eles conheceram Maria salvando-a de uma gangue de bandidos e como Brandon e Maria se apaixonaram à primeira vista. A velha turma se divertia por aí, fazendo o que queria, incluindo seguir Brandon em seu primeiro encontro com Maria. Harry estava feliz com sua vida, pois estava livre para fazer o que queria. Quando Harry se recupera de um acidente de carro, Grave aparece e aponta uma arma para ele. Ele puxa o gatilho, mas ficou sem balas. Os dois começam a rir como costumavam fazer antes de seus dias de sindicato.

Harry e Grave (Brandon) sentam-se nas ruínas do bar de Jolice e Harry tenta descobrir o que deu errado. Eventualmente, ele decide pôr um fim em tudo e devolve a arma velha a Brandon e tira-a com a intenção de atirar uma na outra. De repente, eles são atacados por capangas da Millennion e ambos revidam, com Brandon protegendo Harry com seu próprio corpo em um exemplo. Mika pede a Biscoe para interromper o ataque, mas ele se recusa e a dispensa friamente porque Brandon está do lado de Harry. Mika então foge em uma tentativa desesperada de chegar onde os combates acontecem. De volta ao local dos combates, a polícia armada é vista com armas anti-necrólise. Uma granada é jogada no prédio, o que causa o colapso. Mika vê a fumaça subindo ao mesmo tempo em que Biscoe a alcança em um carro e decide levá-la para Brandon. Brandon acaba protegendo Harry de ser esmagado sob uma laje de concreto. Brandon revida, mas leva uma bala Anti-Necrolyze até o joelho. Harry rapidamente joga sua arma para Brandon, mas isso o torna notável para os agentes e faz com que eles concentrem seu fogo nele. Brandon solta um rugido angustiado ao ver o corpo de Harry caindo no chão. Então a cena muda para Biscoe, que ordena que seus homens parem o ataque. De volta à cena da luta, o tiroteio parou e Brandon cai, com a perna direita quebrando. Harry se aproxima dele, e Brandon admite que nunca pode atirar em Harry, seu melhor amigo. Harry começa a chorar. Brandon deseja voltar aos velhos tempos em que estavam felizes e sugere que eles deveriam atirar um no outro. Mika chega ao local e, com um sorriso choroso, diz que ela e Brandon são e sempre serão uma família. Depois disso, os créditos rolam quando os amigos e a família falecidos de Brandon e Harry os chamam, e Mika é ouvida chamando Brandon no final. A cena final mostra como Brandon e Harry se conheceram quando crianças, e quando a tela fica preta, podemos ouvir Mika dizer "Bem-vindo em casa".