劉永福的青年時代和所有農民一樣，種地過活。他依靠堂兄弟在平福開墾荒地進行耕種，但無論怎樣賣力氣苦幹，到最後仍是食不果腹。相比之下，那些清朝的官老爺隻知作威作福，窮奢極欲，毫不理會老百姓死活。身強力壯的劉永福看到這種情景，毅然投身於農民起義軍的隊伍當中去。1857年（鹹豐七年），劉永福兄弟加入天地會，在首領吳淩雲部屬鄭三手下當上了先鋒。
吳淩雲領導的這支起義軍與太平軍的戰鬥遙相呼應，經過對地主階級的征戰之後迅速擴大起來，成為一支勁旅，但也由此為清朝的圍剿埋下了根源。此時，清軍正忙於圍攻太平天國，無暇南顧。當太平天國天京被拿下之後，朝廷終於騰出手來收拾廣西這支農民軍，最後首領吳淩雲犧牲。1866年，劉永福帶領二百餘人同吳業終（吳鯤）彙合，經過擴充整編，組成一個旗，劉永福被任為旗頭。這天，劉永福的隊伍在歸順州（今靖西）安德圩的北帝廟駐營，他看見北帝神像傍邊的周公手執著一麵繪有“北鬥七星”圖案、鑲有狗牙白邊的黑色三角旗，就仿造黑旗作自為己隊伍的旗幟。從此以後，人們就將這支高舉黑旗的軍隊稱為黑旗軍。
1867年秋，廣西提督馮子材接到朝廷命令，剿滅廣西的農民軍。幾個回合鬥爭下來，農民軍傷亡慘重，軍糧軍餉都成了難題。這支隊伍的幾個領袖商量之後，因為目的不同，最後決定分道揚鑣，各自率部轉移到越南。劉永福帶領二百黑旗士兵，從歸順州的波鬥翻越崎嶇的大嶺進入越南蘇圩，此後，劉永福不斷擴大自己的地盤，相繼拿下了安禮、高平、左大、六安等地，直接與雲南隔河相望的保勝（老街）相接。
1867年，法國侵略者強行侵占了越南的南半部之後，就瘋狂地發動對越南北部進攻，夢想滅亡越南，進而從西南入侵中國，建立一個所謂“偉大的法蘭西東方帝國”。那時，越南阮氏王朝“政令酷虐，民不聊生”弄得田園荒蕪，衰微破敗，麵對法國的侵略，隻好采取屈辱求和，妥協投降的態度。1873年11月，法國殖民主義急先鋒堵布益企圖以武力打通紅河，搜刮我國雲南礦產資源、開辟進入西南腹地新商路的陰謀受阻後，法國當局派安鄴帶兵一百八十名和兩艘炮艦於11月20日晨突然轟擊河內，越南總督阮氏知方奮起抵抗。但武器差劣，士氣不振，不堪一擊。法國侵略軍配備有最新式的精良武器，諸如來福快槍、卡乞開司機關槍、開花彈大炮等。安鄴命令輪流開機關槍掃射，發炮轟擊城牆。阮知方的兒子阮林在城頭被炸斃，阮知方受傷被俘，拒醫絕食而死，以示不屈。越王迫不得己，派人分別往諒山和保勝請求清朝政府出兵援助。但清軍無動於衷，隻有劉永福見義勇為，挺身抗暴，親自率軍二千，翻越宣光大嶺，日夜兼程，南下抗法。
12月21日黑旗軍在河內郊外羅池與安鄴殖民軍正式開戰。法軍按照步兵戰術，排好一字雁隊，分前後兩排，前排鵝步持槍瞄準射擊，後蹲跪填裝彈藥，輪番射擊，交替前進。劉永福傳令全軍沉著應戰，先派出一部分兵力，向左右兩側運動，貓腰躍進，迂回包圍；接著又出動敢死隊正麵迎敵，接火後洋裝敗退，誘敵深入伏擊圈。法軍大搖大擺直上。黑旗軍放下米袋，裝上刺刀，霎時間伏兵四起，殺聲震天，展開慘烈的血刃戰，打得法軍抱頭鼠竄，敗不成陣，爭先恐後縮回河內城。黑旗軍的先鋒營吳鳳典橫衝直砍，如入無人之境，尾追安鄴，擊斃這個不可一世的戰爭狂人，其部屬百餘人辦成了刀下鬼。法軍被逼退出河內，這是劉永福捍衛國疆，支援友邦抗法的首次戰功。越王擢升劉永福為三宣副督，又賜印信一顆，文曰：“山西、興化、宣光副提督英勇將軍印”，以彰表功績，並命劉永福扼守紅河兩岸。
河內首戰全勝，越南境內稍得粗安，推遲了法國殖民者並吞越南，覬覦中國的日程。但事隔十年之後，法國國會於1883年撥款五百五十萬法郎作侵越經費，任命殖民頭子李威利為侵略軍總司令，率領法軍二千人先後攻占河內和南定。接著又分兵進犯越南國都順化及北寧、山西，局勢岌岌可危。越軍望風披靡，清軍觀望不前。劉永福滿懷“為越南平寇，為祖國屏邊”的宏願，於5月6日率領黑旗軍三千挺進河內，會同越軍把河內城圍得水泄不通，並且發揮近戰、夜戰的優勢，誘敵深入，進行短兵相接的肉搏戰，先下令大刀隊執行巧計引敵上鉤的戰術。法軍衝殺出城，黑旗軍大刀隊紛紛撲地臥倒，速將預備好的豬血、朱砂塗在身上，假裝戰死。待法軍呼嘯而過後，猛然翻身躍起，使敵兵腹背受敵，陷入重圍，槍炮已不起作用，被砍得人頭滾地，鬼哭狼嚎。法軍統帥李威利也被大刀隊剁成肉餅。這就是舉世聞名的紙橋之役。越王為了表彰劉永福紙橋大捷的軍功，晉升他為三宣提督，加賜一等義勇男的爵號。