刘永福和伙伴们决定去投奔义军，可是当时广西义军有很多支，去投哪一支呢？经过七嘴八舌的一番议论，刘永福最后拿主意去投奔迁隆州的吴凌云部义军。那时，吴凌云部义军人多势众，粮饷充足，声势浩大，屡次打败前来镇压的清军。
确定了投军目标，刘永福和同伴们约好在第二天深夜，趁夜深人静，悄悄地向吴凌云义军的所在地——迁隆州进发。第二天深夜，刘永福和同伴离开家乡，前往迁隆州。等他们千辛万苦赶到迁隆州时，吴凌云已经率义军主力攻打太平府去，迁隆州的守将郑三代表吴凌云接待了刘永福一行。此后，刘永福等人就在郑三手下大张旗鼓地干了起来。
刘永福作战勇敢机敏，屡建奇功，平时对义军兄弟热情相待，乐于助人，深得人心。不久，郑三就任命刘永福为先锋，让他冲锋陷阵打头阵。由于刘永福有勇有谋，名声远扬，很快又得到了吴凌云的重视，成为全军有名的勇将。
1863年，吴凌云牺牲，其子吴亚忠率残余义军摆脱清军的追剿，继续坚持斗争。刘永福率领的军队也只剩下数百人，但他告知吴亚忠，要继续同他一起与贪官污吏和清朝军队做斗争，继续奉吴亚忠为首领。吴亚忠为了表示信任刘永福，让刘永福指挥自己带来的队伍，而且另组编制。
那是在1865年，刘永福率部下二百多人来到安德圩，投奔吴亚忠带领的义军总队。这一天，安德圩吴亚忠军营里，旌旗招展，鼓乐齐鸣。吴亚忠亲自率领义军大小头目迎接刘永福。双方相互介绍寒暄过后，刘永福对吴亚忠说：“我带了这么多兄弟来投靠你，这给你增添负担了。”刘永福这样说，是带有投石问路用心的。
“久闻刘兄机智勇敢，多谋善策，是难得的人材，况且现在正是用人之际，有刘兄及众兄弟的加入，我们反清大业成功之期指日可待”，吴亚忠意挚情真地对刘永福说。这非常出乎刘永福的意料，他半悬着的心这才落了地。
为了表示对刘永福的信任，吴亚忠让刘永福指挥自己带来的队伍，他对刘永福说：“这二百多个兄弟，既然是由你带来的，以后就由你全权指挥，其他任何人都不得插手。”
“那我就谢谢大哥的信任，以后我及众弟兄一定听从大哥的指挥，冲锋陷阵，血洒战场，在所不辞！”刘永福急忙回答说。
自从参加农民军以来，由于刘永福自己没有一支武装力量，所以，几年来，他总是仰人鼻息，寄人篱下，无法实现自己使广大穷苦兄弟脱离苦海的抱负，觉得很对不起同甘共苦的兄弟，心里非常不是滋味，他常常陷入忧郁、苦思冥想之中。
这次刘永福见吴亚忠以诚相待，深为感动，特别是对自己的人马，能够得以单独编制，由自己指挥，更是大喜过望。他终于实现了自己多年的夙愿。从此，刘永福有了一支由自己领导和指挥的部队了。
吴亚忠设宴为刘永福接风洗尘之后，便传令将安德圩白帝庙作为刘永福部临时驻扎的地方。刘永福回到白帝庙，将吴亚忠对自己的态度详细地向兄弟们作了介绍，大家听了都非常高兴。
“兄弟们”，刘永福环视了一下众兄弟，接着说道：“从今以后，咱们就是一支独立的部队，应该有自己的旗帜，所以我想举行一个建军祭旗大典。”
大家听后都纷纷表示赞同，那么，用什么旗作为自己部队的标志呢？大家你一言我一语，开始议论起来，说什么的都有，方案五花八门，最后大家都将目光集中到刘永福身上。
刘永福从大家期待的目光中，知道兄弟们是在想听听自己的想法，更看到了兄弟们对自己的信任。于是，他抬起头，在白帝庙内打量了一番——这白帝庙里供奉着三尊神像，北极玄天大帝居中，右侧是花婆神，左侧是周公。周公手拿一面黑旗，旗身是三角黑布，边沿镶狗牙形白布，旗上绣有北斗七星。附近几十里的人都来白帝庙中求神赐福，听说庙里的神很灵验，特别是周公手里的七星旗很灵验，而且周公是西周重臣，懂军事，多智谋。因此，刘永福慢慢说道：“我听说这白帝庙中周公手里的七星三角黑旌很灵验，不如按此旌放大制作一面，作为咱们部队的旌号。”这一建议得到大家的一致赞同。刘永福于是让人按照庙里周公手中的七星黑旗，放大制作了一面，作为自己部队的军旗，既符合自己“黑虎将军”的称号，又可以让周公保佑自己多打胜仗。于是，大家商定，等部队一切安顿好之后，即选择一个黄道吉日，举行建军祭旗大典。
这一天早饭后，刘永福让人把白帝庙四周打扫得干干净净，一尘不染，并传令午饭后举行建军祭旗大典。午后的空气如同凝固一样，一丝风也没有，连树梢也纹丝不动，天空中虽然飘浮着几朵白云，可难以遮挡那火辣辣的阳光，直射而下的阳光使得天空好像在下火一般。
随着一声号角划过沉闷的天空，白帝庙前顿时人声鼎沸，一队队义军在庙前分两厢站立，个个精神抖擞，斗志昂扬，刘永福器宇轩昂地站在庙前台阶上，他双目炯炯有神，直视前方。他身后竖起一面崭新的三角黑旗，旗面正中央绣着一个斗大的“刘”字，“刘”字四周绣有北斗七星，边沿镶着狗牙形的白边。
歃血为盟的建军祭旗大典，在一片锣鼓声和欢呼声中开始了。刘永福走下台阶，与前排兄弟一一握手，并不时地向后排兄弟拱手示意，然后又重新回到原来的位置，他从腰间拔出一把锐利的尖刀，割破自己的食指，殷红的鲜血滴滴答答地流入盛有米酒的大碗之中，数百名义军兄弟也一一照做。
盛典正在举行之时，突然，天空中乌云密布，狂风骤起，随着一声巨雷响过，大雨倾盆而下，刘永福和义军兄弟们毫不介意，他见众兄弟照自己的样子做完之后，一扬头，将混着鲜血与雨水的米酒一饮而尽，随后众兄弟也都纷纷照做。这样，歃血结盟祭旗大典在大雨中结束。
因为刘永福军队以黑旗为旗号，所以，人们称其为“黑旗军”。
刘永福建立了黑旗军，决心将它训练成一支精良队伍，作为吴亚忠义军部队中的骨干力量。黑旗军初建时，总兵力只有数百人，刘永福为统帅，另有百余名大小首领。这队伍人数虽不算多，但个个都是跟随刘永福多年的兄弟，有丰富的作战经验，战场上能以一敌十，战斗力极强。
黑旗军训练有素，刘永福训练士兵十分严格，将十八般武艺有步骤地向士兵们传授。每一名教官都认真负责，精心传授；每一个士兵都苦练本领，持之以恒。刘永福平常对部下管束很严，要求他们勇敢杀敌，不准骚扰百姓。黑旗军战士，大多是贫苦农民，素质很好，在刘永福的领导下，经过几次战火的洗礼，愈战愈勇，愈战愈强，成为一支极富战斗力的部队。刘永福还严格要求士兵要勇敢杀敌，遇有战斗，将领退则斩将领，士兵退则斩士兵。这些训练，使得黑旗军战斗力不断加强。
这一天，吴亚忠邀集刘永福和其他将领商量攻打南雁事宜。南雁离吴亚忠义军驻地有四五十里，道路崎岖险要，清军凭险扼守，和义军对峙。附近其他地区的清军依仗南雁的清军，也互相呼应，对义军构成严重威胁。因此南雁一破，各地清军就会望风而逃。
刘永福自告奋勇，要求黑旗军出征打先锋，吴亚忠率大队人马在后接应。吴亚忠素知刘永福能征惯战，黑旗军无坚不摧，便高兴地任命刘永福为先锋，率黑旗军为先头部队，攻打南雁，自己率大队人马随后赶到，猛攻敌人。
黑旗军将士赶到南雁，很快和清军交起手来。清军凭借险要地形固守，黑旗军利用巨石树木作掩护，不断向前冲击，终于将清军赶出南雁关口。清军狼狈逃窜，退入南雁城中。刘永福下令黑旗军将士围城，等候吴亚忠大军前来。
吴亚忠率领大军赶到，见刘永福初战告捷，已将清军逼进孤城，欣喜异常。随后下令大军将南雁城围得水泄不通。相持数日，南雁城中的清军自知不是义军对手，派人出城，表示投降，并交出城池。南雁清军投降，附近各地清军逃跑的逃跑，投降的投降，义军很快占领了这片地区。
南雁这一仗，黑旗军为取得胜利立下了大功。此后黑旗军声威日壮，清军都不敢与黑旗军交战，因为黑旗军“皆敢死”，“英勇绝伦，每阵争先”。一些地主团练企图用高官厚禄收买刘永福，将黑旗军编入自身武装，均遭到刘永福严厉的痛斥。
在战火的洗礼中，黑旗军不断壮大，逐渐远近闻名，令敌人闻风丧胆。同时，刘永福也从一个普通的农民义军士兵，逐渐成为一个比较成熟的军事指挥员。
