黑道上的小混混阿西莫夫从敌对组织那里抢到了大量毒品「血眼」，也因此被通缉。他的恋人卡特琳娜希望能够用卖掉毒品换来的钱去火星过幸福的生活。阿西莫夫使用眼药水打倒了追杀他们的一批敌人。然后，就像占卜师布尔预言的那样，斯派克和阿西莫夫相遇了。未能得手反而险些被暗算的斯派克在北边的街道末端再次追踪阿西莫夫。斯派克驾驶着「剑鱼II」追击着逃亡的两人乘坐的机体一直到了大气圈以外。最后明白无法逃亡理由的卡特琳娜把枪口对准了邻座的阿西莫夫……

高个子、蓬松头、功夫了得的赏金头目阿布杜尔·哈奇姆从研究机关抢走了一只秘密开发的数据犬，准备进行巨额的交易。结果，那只狗经过一系列意外离开哈奇姆来到了斯派克手中。斯派克和杰特打算以狗为诱饵引出哈奇姆，接着研究机关的人也加入到那里。围绕柯基犬的三方追逐的闹剧就这样展开了……最后，具有极高智商、又跳又叫的叫做艾因的柯基犬也成为了BEBOP号的一员。

被认成传说中的女赌徒爱丽斯的菲被带到了火星附近的空间站赌场「火星的蜘蛛」。赌场的老板戈登以帮助偿还6亿债款为条件让菲去帮忙完成一桩交易。作为交易品的筹码里储存了人类历史上最强的、能够破解一切密码的程序。然而那颗筹码又阴差阳错地落到了和杰特一起来赌场游玩的斯派克的手里。戈登为了抢夺筹码和斯派克展开了宇宙中的枪战。混乱中，菲带着现金逃走了。

斯派克和杰特在木卫三的餐厅追捕其他赏金头目的时候，偶然遇到了环境保护恐怖组织「星际战士」的成员。瞄准的猎物丢了，斯派克顺手将「星际战士」的头目、被其他成员称作「妈妈」的土温克·玛利亚·马杜克这个更大的猎物抓回了BEBOP号。紧接着，他们与在宇宙中漂流的菲又再次相遇了。另一方面，失去了「妈妈」的「星际战士」们以能够把人变成猿猴的病毒「Monkey Business」威胁木卫三政府取消了对「妈妈」的赏金。斯派克等人非常不情愿地放走了「妈妈」，而「妈妈」为了报复立即向木卫三发射了带有病毒的导弹。在位相差空间内，斯派克一行再一次被导弹折腾得手忙脚乱……

「红龙」的干部毛恩来被人以高额赏金悬赏。过去受到过毛恩来照顾的斯派克看到这个消息后立即展开了调查。然而在那之前，毛恩来就已经被斯派克在「红龙」的死对头比夏斯杀害了。另一方面，打算独占赏金的菲也落入了比夏斯的陷阱。比夏斯以菲为人质叫出了斯派克，两人在教堂再次相遇了。

代号长颈鹿的赏金头目一直在跟踪一个坐在轮椅上的人和推着轮椅的少年。尾随而来的斯派克最后接住的从高楼掉下的人却是奄奄一息的长颈鹿。临死前的长颈鹿交给斯派克一块宝石，并让他拯救某人。与名叫「文」的少年再次相遇的斯派克终于了解了事情的真相。原来文在50年前因为位相差空间门事故拥有了不老不死的肉体，而坐在轮椅上的长颈鹿的过去的战友、代号斑马的植物人则成为了文用来掩饰身份的道具。即使头部中弹也能从容逃走的文已经成为了一个不折不扣的冷血杀人魔。决心「拯救」文的斯派克把从长颈鹿那里得到的宝石磨成子弹放进了枪膛……

追踪携带大量危险炸药的赏金头目德卡的途中，斯派克与女卡车司机V.T.相遇了。V.T.的本名被谜团所保包围，如果能够说中她的名字就可以得到一笔巨款。V.T.和斯派克告别后，偶然发现了德卡乘坐的卡车，并尾随其后进入了小行星带的危险的废矿山。德卡在突然发生的爆炸中死亡，V.T.也在爆炸中昏了过去。由于德卡的卡车中携带了大量炸药，废矿山随时都有着一触即发的危险。闻讯赶来的斯派克以性命为赌注终于使得众人脱离危险。之后，斯派克也意外地得知了V.T.的本名。

为了拯救由于金星病而失去视力的妹妹斯特拉，洛可·波纳罗冒着危险，从自己所属的皮卡罗犯罪集团中偷走了能够治疗金星病的特效药草「Grey Ash」。逃亡途中，与斯派克相遇的洛可将药草委托给斯派克，然后消失了。感到为难的斯派克找到了洛可的妹妹斯特拉，了解了洛可纯粹为了妹妹的心情。斯派克来到和洛可约定的地点，皮卡罗一伙也在那里等待着。激烈的枪战中，洛可被打中胸部丢掉了性命。被托付了「Grey Ash」的斯派克为洛可的妹妹准备了手术费，同时带去的还有哥哥死亡的讯息。

人造卫星在地球上描绘着图案。认为是黑客所为的地球政府为此提供了赏金，BEBOP号也由此来到了地球。立刻开始寻找黑客的杰特和菲得到了名为「激进爱德华」的人物的情报。不过关于其真面目却不得而知。正在这个时候，被称做「激进爱德华」的天才黑客爱德通过网络访问了人造卫星，并且和人造卫星的AI程序「小电」成为了朋友。爱德与BEBOP号通讯，告知了「小电」就是绘制巨画的犯人。之后，斯派克一行在爱德的帮助下取得了「小电」的数据，但最后却因为犯人不是生物而没有得到赏金。取而代之的是爱德也成为了BEBOP号上的伙伴。

木卫三的海港迎来了又一个冬天。在回到木卫三老家的途中，杰特凝视着陈旧的怀表，回想起了往事。过去的杰特是一个执着并且固执的警察，一起生活的还有他的恋人阿丽莎。然而在某一天，阿丽莎突然丢下杰特独自离去。到达木卫三的杰特和阿丽莎再次相遇，同时遇到的还有正在被通缉的阿丽莎的男友林特。杰特为了履行自己的义务、同时和过去做一个了断，追赶着逃亡的阿丽莎和林特。被逼到末路的阿丽莎用颤动的手臂把枪口指向了杰特……

杰特在BEBOP号的仓库遭到不明物体袭击，被咬后出现了一个奇怪的伤口。紧接着，菲和艾因也遭到了袭击，都倒在了地板上。爱德也失踪了。为了查明真相，斯派克全副武装，开始了与谜之生命体的战斗。终于制服了怪物的斯派克发现这个生物是从放置了几年的冰箱里产生的，于是打算将冰箱扔到飞船外的宇宙空间，而在最后关头又被突然出现的宇宙生命体袭击了。在失去重力、自动航行的BEBOP号中，斯派克一行人跳起了华尔兹……

比夏斯因为要和以前的战友进行眼药毒品「红眼」的交易而来到了木卫四。另一方面，斯派克和菲也因为各自的理由离开BEBOP号造访木卫四。菲在酒吧中和吹奏萨克斯的美男子格林邂逅，随后被带去了格林的住所。斯派克则在木卫四的雪地与比夏斯再次对峙。斯派克被以前的义弟林一枪击中胸口，倒在了雪地上。另一方面，菲无意中听到比夏斯给格林打来的联络电话，拿着枪闯进浴室却看见了格林女性化的身体……

格林在以前的泰坦战争中对一同作战的比夏斯充满了同志般的信赖，然而比夏斯的背叛使得他进了监狱，并且因为染上药瘾的副作用而有了女性化的身体。一直策划着对比夏斯复仇计划的格林终于得到了这次机会，在木卫四和比夏斯再次相遇。终于从被麻醉弹的麻醉中醒过来的斯派克也加入其中，三方在空中展开了混战……

位相差空间门的黑客事件接二连三的发生。然而无论抓住多少现行犯，却没有主谋「棋王赫克斯」的半点消息。然而以意外的方式得到了情报：爱德正在玩得不亦乐乎的网络国际象棋的对手正是「棋王赫克斯」。斯派克和菲朝着「棋王赫克斯」的数据发生来源、小行星带的废料岛出发了。2人在那里找到的是衰老不堪，以国际象棋为唯一生活目的的老人。50年前参与位相差空间门开发的赫克斯，为了「门」在技术上存在的安全隐患而作出的警告，导致了50年后的这一系列黑客事件。

刚从冷冻睡眠中苏醒过来的菲对于周围的一切充满了陌生感。维特尼·哈格斯·松本是支撑菲内心的男人、是愿意守护背负了巨大的欠款的菲的男人、也是为了帮助被讨债人追赶的菲，牺牲了生命的男人。当菲在BEBOP号上回想起3年前往事的时候，杰特带回来一个因为婚姻诈骗而被通缉的赏金头目，而那个男人正是维特尼。原来维特尼是为菲进行解冻手术的医生的外甥，3年前他所做的一切是为了能够将自己的欠款转到菲的名下。菲为了取回冷冻睡眠以前的记忆，不惜与斯派克和杰特为敌，强行将维特尼带出了BEBOP号。然而，关于菲的过去维特尼全然不知……

被星际押送的乌代等死刑犯杀死船上的所有警察、夺取了囚犯运输船。从警察时代的同伴法德那里听到这个消息的杰特感到左臂又疼痛起来。乌代正是让杰特失去左臂的仇人。杰特再次成为了警察时代的绰号所形容的那样，成为了一条咬住就不会松口的「黑狗」，开始执着地追踪乌代。然而，当杰特突破重重阻碍终于和乌代面对面时，却听到了令他难以置信的真相。原来当年让杰特中埋伏并射击其左臂的正是杰特的搭档法德。突然出现的法德击毙了乌代。对峙的杰特和法德经过短暂的沉默后，互相扣动了扳机……

蘑菇商人多米诺因为贩卖毒蘑菇成为了被通缉的赏金头目。被多米诺的飞船撞到的BEBOP号来到了木卫一进行修整。爱德受到几天没有进食的斯派克一行的委托出去寻找食物，在路上碰到了为了给哥哥报仇而追踪多米诺的青年夏夫特以及为了赏金而追踪多米诺的女赏金猎人科菲。一番喧哗后、爱德带着多米诺丢下的毒蘑菇，作为赠品分给了缺钱而饿肚子的BEBOP号上的每个人。食用了毒蘑菇的三人，进入了各自的幻想世界。另一方面，了解了多米诺是赏金头目后，爱德带着艾因再次开始了搜索。夏夫特和科菲的再次加入使得这场大追踪剧再次展开。

不知从什么地方寄来的一盘接收人写着菲的名字的Beta格式录像带改变了众人的生活。以为有人追债的菲再次从BEBOP号逃走了。斯派克和杰特为了能够知道这盘带子中到底有些什么内容而不远万里的来到了地球上的电器博物馆。经过漫长的探索终于得到了录像机和电视的二人满足的回到了BEBOP号上，然而带回的VHS格式的录像机是无法播放Beta格式录像带的。正当二人感到气馁的时候，邮递公司又送来了Beta格式录像机。带子终于可以播放了，菲也在这个时候回到了BEBOP号。原来这盘录像带是少女时代的菲寄给未来的自己的礼物，录象中的菲穿着啦啦队的衣服不断地鼓舞未来的自己。「这天的我，一直在这里支持着你」。

斯派克将爱机「剑鱼II」带到地球上进行好不容易才有一次的大修。而精明强干的修理工杜汉也正是「剑鱼Ⅱ」的原主人。另外一边，追踪星际海盗的BEBOP号也因为偷袭而遭受了重创。于是斯派克驾驶着修复完毕的「剑鱼Ⅱ」独自一人去追击星际海盗。然而在战斗中再次被暗算的「剑鱼Ⅱ」也失去了控制，开始朝地球下坠。已经做好准备迎接死亡的斯派克突然收到杜汉的准备前来营救的消息。而前来营救的古董机正是哥伦比亚号航天飞机……

「Hello，Gentleman」，伴随着台词与发狂的笑声一起出现的，是被称做「疯狂小丑」的神秘刺客东风。他是在ISSP的人体试验中诞生的杀人机器。一个夜晚，刚打完台球的斯派克偶然亲眼目睹了东风的杀人现场。于是斯派克成为了东风的下一个目标。浑身是伤的斯派克在收到东风的挑战书后独自一人来到了约定的游乐场。在那里等待的，是东风恶梦般的攻击。在天真活泼的音乐伴奏下，斯派克勉强地躲避着东风的攻击。但是，结果却总是出人意料的。斯派克的瞳孔，唤醒了东风不详的回忆。一瞬间，斯派克的匕首刺进了刀枪不入的东风的腿。再次体会到久违的疼痛的东风倒在地上像婴儿般地哭闹……

宇宙风水师包朴子的女儿梅花在寻找失踪的父亲。杰特则从即将死亡的包朴子那里收到了神秘的邮件。杰特与梅花，因为不可思议的缘分而联系在一起的二人互相配合，找到了作为发现包的线索的太阳石。也了解到包朴子被困在了位相差空间里。行进途中，杰特告诉了梅花实情。原来包朴子是一个犯罪组织的师爷，曾经是杰特的线人的包朴子想脱离组织却未能如愿，为了家人的安全，包朴子在女儿面前消失了踪影。最后，在位相差空间里，凭借太阳石的力量父女终于得以短暂团聚。

骑着马、戴者牛仔帽、一副牛仔装扮的安迪·冯·德·欧尼亚特，由于总是胡闹与过分自信的性格，与斯派克一起成为了赏金头目最害怕的赏金猎人。这两个人因为瞄准了同一个赏金头目——炸弹狂魔特德·波尔而变的针锋相对。特德坦言自己是为了高尚的理想而进行破坏活动，不过斯派克和安迪却完全听不进去。最后斯派克和安迪把炸弹人扔在一边开始了决斗。

电子移民财团「SCRATCH」的教祖隆迪斯博士被悬赏3800万的巨额赏金。为了赏金只身潜入「SCRATCH」的菲作战失败，向斯派克等人求助。斯派克等开始了对「SCRATCH」的调查，不过却完全找不到一点关于隆迪斯的线索。过了几天，杰特发现隆迪斯只是一个虚构的角色而并非真实存在的人物。以前是黑客，现在处于植物人状态的名叫罗尼·斯潘根的少年编写了隆迪斯这个程序，向着宇宙网络传播。

两个人在荒废的地球上追赶着不断落下的陨石，不断地更新着地球的地图。这两个人就是爱德的父亲阿帕德里和他的助手玛辛泰亚。阿帕德里由于潜心于绘制地图的工作，已经忘记了女儿离开的事情。跟女儿再会的时候，阿帕德里为了追赶落下的陨石又离开了。反复观看录像带，终于取回过去记忆的菲丢下一句「对不起」之后离开了BEBOP号。爱德下定了追赶父亲的决心而离开了BEBOP号，艾因也尾随而去。和最开始一样，BEBOP号只剩下斯派克和杰特两人。

在火星本部密谋反叛的比夏斯被「红龙」的长老们逮捕了。长老们决定将对于组织有潜在威胁的危险分子们彻底排除，于是「红龙」的刺客出现在了斯派克面前。同时，离开BEBOP号单独行动的菲与与被组织追杀的茱莉娅相遇了。各人的命运互相缠绕在一起……不久，刑场上的比夏斯度过了危机，谋反成功，掌握了组织的实权。菲回到BEBOP号，给斯派克带去茱莉娅的口信。斯派克终于能够与一直寻找的人相见了。命运的线，更加复杂地纠结在一起。

被「红龙」追赶的斯派克和茱莉娅来到昔日旧友安妮的杂货店。已经被袭击过的商店中，重伤的安妮在两人面前死去。之后和追击者的枪战中，茱莉娅中枪倒下……回到BEBOP号的斯派克，和杰特和菲告别后，只身一人闯入「红龙」的据点大楼，一口气杀到比夏斯所在的大厦顶楼。「做个了断吧」，「如你所愿」。斯派克的子弹打穿了比夏斯的额头，比夏斯的刀切裂了斯派克的腹部。战斗结束了……

剧场版讲述了在迎接万圣节的火星都市阿尔帕城发生燃料运输车大爆炸事件，四人一狗组合再次出动，但他们不知道，这3亿元的代价，是对抗前所未有的强大犯罪者。