王全斌，并州太原人。
其父奉事莊宗，任岢岚軍使，私下畜養一百多名勇士，莊宗懷疑他心存異志，召見他，他害怕不敢去。
當時全斌十二歲，對他的父親說“：這是因為懷疑大人有别的圖謀才召見您，您讓我去作人質，一定會消去懷疑。
”他的父親照計行事，果然得以保全，于是莊宗把全斌收用在軍中。
到莊宗入洛時，曆任宮内職務。
同光末年，國家有内難，亂兵攻入宮城，近臣宿将都棄甲逃走，隻有全斌與符彥卿等十幾人在宮中抵抗。
莊宗中了流箭，全斌等扶他到绛霄殿，全斌痛哭而去。
明宗即位，補任他為禁軍列校。
後晉初年，跟從侯益在汜水大敗張從賓的軍隊，因戰功升任護聖指揮使，後周廣順初年，改護聖為龍捷，任命全斌為右廂都指揮使。
到了讨伐慕容彥超于兖州時，任行營馬步都校。
顯德年間，跟随向訓平定秦、鳳，于是兼任思州團練使。
不久升為兼任泗州防禦使。
跟從世宗平定淮南。
收複瓦橋關，改任相州留後。
宋初，李筠占據潞州叛亂，全斌與慕容延钊由東路會合大軍進讨，因戰功授任安國軍節度。
诏令他修葺西山堡塞，不到限期就完成了。
建隆四年(963)，與洛州防禦使郭進等人率領軍隊攻入太原境内，俘獲敵人數千人而歸，進克樂平。
乾德二年(964)冬天，又任忠武軍節度。
當天朝廷下诏征伐蜀地，命全斌任西川行營前軍都部署，率領禁軍步兵騎兵二萬人、各州軍隊一萬人由鳳州路進讨。
皇帝召他來看川陝地圖，并且告訴他戰略方針。
十二月，率領軍隊攻拔乾渠渡、萬仞燕子兩個營寨，于是攻下興州，蜀刺史藍思绾退保西縣。
打敗蜀軍七千人，俘獲軍糧四十多萬斛。
接着攻拔石..、魚關、白水二十多座兵營。
先鋒史延德進軍三泉，打敗數萬蜀軍，擒俘招讨使韓保正、副使李進，繳獲糧食三十多萬斛。
不久崔彥進、康延澤等人的軍隊把蜀軍趕過三泉，于是達到嘉陵，殺死、俘虜很多蜀軍。
蜀人阻斷閣道，軍隊不能前進。
全斌打算奪取羅川路攻入，延澤暗裡對彥進說“：羅川路險，軍隊難以齊頭并進，不如分兵修治閣道，與大軍在深渡會合。
”彥進把這個意見告訴全斌，全斌認為正确。
命令彥進、延澤監督修治閣道，幾天後成功，于是進攻金山砦，攻破小漫天砦。
全斌領兵由羅川趕到深渡，與彥進的部隊會合。
蜀人沿長江列陣以待，彥進派張萬友等攻奪敵人的橋梁。
正遇天黑，蜀人退保大漫天砦。
到天明，彥進、延澤、萬友分三路進攻，蜀人出動全部精銳部隊來迎戰，又大破蜀人，乘勝