在上谷扯旗造反,神武便和志同道合者参加了他的队伍。由于瞧不起杜洛周的行事,私自与尉景、段荣、蔡俊等谋划,试图杀死杜洛周,没有成功,而遭杜氏的骑兵追捕。文襄帝及魏永熙皇后两人年纪都小,武明皇后坐在牛背上抱着这两个孩子。文襄几次从牛背上滑落下来,神武准备射死这个儿子好快些逃走。武明皇后恳求段荣救助,多亏段荣夺下神武手中的弓箭,文襄才幸免于死。神武投奔葛荣,又逃亡到秀容,归顺了尔朱荣。早些时候,刘贵服事尔朱荣,极力赞誉神武之美,此时才得见面,由于疲劳憔悴,没有引起尔朱荣的惊奇。刘贵便帮神武更衣换鞋,又一次见了面。继而跟着尔朱荣进到了马厩,厩中关着匹烈马,尔朱荣命令神武将它绑缚起来。神武未用马络头就捆绑住了,而且马一直是服服贴贴的。完事后,站起身来说:“制服恶人就像降服这匹马一样。”尔朱荣便请神武坐于椅子上,摈除左右向他请教时事。神武说:“听说您在十二座山谷里喂养着马匹,以马的颜色划分为群,如此做有何用意?”尔朱荣说:“你尽管谈你的高见吧。”神武说:“当今天子愚笨懦弱,太后淫乱,小人专权,朝政混乱,以您的雄才武略,乘此良机作为一番,讨伐郑俨、徐纥,清除帝侧,成就霸王之业不过是举手之劳。这便是我贺六浑的看法。”尔朱荣大喜过望,从中午一直谈到深夜,神武才告辞离去。从此之后多次参预机密。后随尔朱荣移据并州,入扬州邑人庞苍鹰宅,住在圆形草屋中。每次从外边回来,即使他还在很远的地方行走,屋主人都能听到十分响亮的脚步声。苍鹰的母亲多次看到草屋顶上赤气冲天。有次苍鹰打算潜入神武的草屋,却被一执刀的青衣人拦住,叱问道:“为何触犯大王?”说完,便没了身影。苍鹰开始惊异了,曾密密地窥视,只见一条赤蛇蟠卧在床上,因而更加惊讶。于是宰牛割肉,以厚礼相待。苍鹰之母请求神武做自己的义子。到神武得志,将苍鹰的住屋作为寝宫,唤作“南宅”宽门大户,屋室高敞,他曾经居住过的茅草屋,其墙则用石灰涂抹,认真加以保护,到文宣帝时便成了宫殿———不久,尔朱荣便任命神武做了亲信都督。
此时,北魏孝明帝不满郑俨、徐纥等人逼迫灵太后的行为,但却不敢下诏制裁,就偷偷下令尔朱荣举兵围攻都城。尔朱荣指派神武为前锋。军队抵达上党,明帝又秘密下诏,命令停止前进。到明帝突然驾崩时,尔朱荣才举兵进入洛阳,准备趁机篡政。神武进谏,怕他不听,就请铸铜像卜其吉凶,铜像没有铸成,因此尔朱荣也就停止了篡权活动。魏孝庄帝即位,由于定策的功劳,封神武为铜。。伯。尔朱荣攻打葛荣,命令神武开导晓谕七个称王的盗贼归服。后同行台于晖在泰山打垮了羊侃,又很快在济南与天元穆一块大败邢杲。升官为第三镇人酋长,经常出入于尔朱荣的军帐。尔朱荣曾向左右打听说:“假如哪天没了我,谁可顶替我统帅军队?”众人都推尔朱兆。尔朱荣说:“这正好可以让我带领三千骑兵返归,能够代我主大事的只有贺六浑这个人。”并告诫尔朱兆:“你不是他的对手,最终你会被人家制服的。”就任命神武做了晋州刺史。神武为刺史后大力集聚财粮,安排刘贵贿赂收买尔朱荣手下的重要人物,目标一个接一个地实现。这时州库的屋角无缘无故地发出声响,神武为此惊异,不多时日,孝庄帝诛杀了尔朱荣。
尔朱兆率兵从晋阳赶赴洛阳,征召神武。神武打发长史孙腾借口绛蜀、汾胡诸地将要反叛,情况危急而予以推辞,尔朱兆就怀恨在心了。孙腾回来向神武作了报告。神武说:“尔朱兆领兵犯上,是最大的盗贼,我不能长期侍奉他。”从此开始便有了图谋尔朱兆的打算。尔朱兆一进入洛阳,押解着孝庄帝往北而去,听到这个消息,神武大吃一惊。又派孙腾假装成祝贺尔朱兆的使者,趁机秘密打听孝庄帝的囚拘之所,准备偷抢出来,以举大事,却没有成功。于是写信向尔朱兆晓以大义,说不应当拘押天子而让天下人唾骂。尔朱兆置之不理,杀了孝庄帝,同尔朱世隆等人立长广王晔为帝,改年号为建明。封神武为平阳郡公。当费也头纥豆陵步藩侵占秀容,紧逼晋阳时,尔朱兆召唤神武。神武准备前往,贺拔焉过儿请求不要赴命好使尔朱兆陷入疲困。神武就故意延滞逗留,还借口河上无桥没法渡过。步藩兵强马壮,尔朱兆大败逃跑。当初,孝庄帝处死尔朱荣,预料到他的党徒一定会有反叛之心,就秘密诏令步藩偷袭他的后部。步藩打败尔朱兆后,于是军队人数增多,力量更大,尔朱兆又向神武求救,神武暗地里想谋取尔朱兆,又考虑到步藩在后部的祸患难以消除,于是就同他配合,竭尽全力打败了步藩。步藩死后,尔朱兆十分感恩戴德,两人便结拜成了兄弟。这时世隆、度律、彦伯共同执掌朝政。天光占据关右,尔朱兆盘踞并州,仲远领有东都,各自拥兵为暴,却害苦了老百姓。
葛荣部众流亡入并、肆两地者达二十多万,却遭契胡凌辱残害,无法生活,被迫举行了大小二十六次反叛,受屠戮者过半,但他们依然处于无休止的被掠夺之中。尔朱兆对此十分担扰,就向神武请教处置的办法。神武说:“六镇造反留下来的人,不能全部杀掉,应该挑选您的心腹之人悄悄地统领起来。如再造反,只向其头目问罪,那么想造反的人就减少了。”尔朱兆说:“是呀,谁可担当此项任务?”当时坐在旁边的贺拔允听说后,马上向神武请求这个差事。神武向其猛击几拳,打断了他的一颗牙齿,数落说:“天柱在世时,我辈老老实实,像鹰犬一样地听使唤。那么今天的安排全在大王。你阿鞠泥胆敢诬下欺上,我请求大王杀了你!”尔朱兆以为神武忠诚,就委以这项重任。神武感觉到尔朱兆喝醉了,担心他酒醒后起疑心而生反悔,马上出门,向人们宣布自己受尔朱兆之托统领本州镇兵,可以聚集汾东待命。接着在阳曲川建立军旗,布置战阵。有个叩击军门的男子,头裹红巾身著红袍,自称是梗杨驿站的人,愿意服侍左右。神武问他有何特长,答曰力大无比,常在并州城里殴打那些杀人凶手,因此留他做了亲信。兵士们一向讨厌尔朱兆而喜欢神武,在这个时候纷纷前来投靠。过了不长时间,神武再次派遣刘贵向尔朱兆提出请求,以并、肆等地连年天灾,迫使降户挖掘黄鼠作为充饥之食,所以人人面有菜色,白白玷污了人家的土地,希望让这批人前往山东谋生,等待温饱之后再作安置,尔朱兆接受了神武的建议。可是尔朱兆的长史慕容绍宗不同意,进谏说:“这样不妥吧?如今天下大乱,人人都有野心,何况高公雄才大略,又手握重兵,您将无法驾驭。”尔朱兆说:“我们是结拜兄弟,没有什么担忧的。”绍宗说:“亲兄弟都会互相猜疑,结拜兄弟就更加难免了。”此时尔朱兆的左右都接受过神武的贿赂,便乘机攻击绍宗与神武早有矛盾,这样尔朱兆就拘捕了绍宗,并催神武赶快上路。神武从晋阳动身出了滏口。途中碰到了尔朱荣寡妻乡郡长公主,长公主从洛阳带了三百匹马来,神武全部夺归己有。尔朱兆听到这个消息,马上释放绍宗,并向他请教对付神武的办法。绍宗说:“他还是大王的掌中之物。”尔朱兆亲自追赶神武,抵达襄垣,恰逢漳水暴涨,桥被冲坏。神武在漳河对岸解释说:“我借用长公主的马匹,没有别的企图,只是为了防备山东的盗贼而已。大王您听了公主的话,亲自追我,眼下不渡过河来狠狠给以训斥的话,兵众便生叛离之心。”尔朱兆自称没有这种想法,便骑着马渡过河来,与神武一同坐于军帐之下,道歉后,拔出刀还伸过头来,请求神武砍杀。神武号哭着说:“自从天柱遇难后,我贺六浑再也没有靠山了。我祝愿大王您千岁万岁,好让我永远为您服务。如今有人这样挑拨离间,大王您为什么还要讲出这样的话来?”尔朱兆掷刀于地。于是杀白马结盟,再为兄弟。神武留尔朱兆住下,还设宴款待。尉景事前埋伏兵士试图将其生擒。神武咬破胳膊制止说:“现在杀死他,他的部众一定要跑回去聚集兵马报复的。我们的士兵饥饿,战马羸弱,不可抗衡,倘若此时英雄豪杰振臂一呼,那么祸害就会更加厉害。不如姑且让他多活几天。尔朱兆虽然力大敏捷、凶残却无谋略,不是我们的对手。”第二天,尔朱兆返回军营后,又召请神武,神武准备骑马前往,孙腾拉了拉他的衣服,神武就没有上道。尔朱兆隔着漳水大声谩骂,之后跑回了晋阳。尔朱兆的心腹念贤带领降户人家分别组成营伍,神武假装亲近,借口观看他的佩刀,顺势杀掉了他和几个随从,其余的侍卫吓得赶快逃走。因而士众都十分喜悦,更加希望跟从神武。当初,魏真君的侍从文人上书,说上党有天子气,位居壶关大王山。太武帝南巡抵制压迫这种天子气,垒积石块成为三堆,截断北侧的凤凰山,破坏了它的形体。后来定居于晋阳的上党人,称自己的住地叫“上党坊”事实上,神武就住在这里。等到行进到大王山,驻扎了六十多天才开拔。快出滏口时,更是注意约束部众,力争丝毫不犯。从麦地边走过,神武则步行牵马。远近的民众听说这些事后,都称赞高仪同治兵严整,更是心悦诚服地归顺了过来。继续前进,屯驻邺地,向相州刺史刘诞借粮,诞不给,神武就将车营租米夺了过来。
魏普泰元年(531)二月,神武率军驻扎信都,高乾、封隆之大开城门等候着,很快就占领了冀州。本月,尔朱度律废元晔立节闵为皇帝,想羁縻住神武。三月,请求节闵帝封神武为渤海王,征召使其入朝觐见。神武推辞未去。四月,又加授神武东道大行台、第一镇人酋长。庞苍鹰从太原跑来投奔,神武任命他做行台郎,不久升任安州刺史。神武率众挺进山东,养育兵士,修理武器,禁止侵占掠夺,更赢得了百姓的归附。神武伪造书信,说尔朱兆拟将六镇人分配给契胡为部曲,因此使这些人十分愁苦怨恨。又制成并州符节,征兵讨伐步落稽。发动万人,准备派遣出去,孙腾、尉景假意请求延缓五天动身,这样反复了几次。神武亲自送到郊外,流着泪向六镇人道别,人们都十分悲痛,哭声震天。神武开导说:“我和你们一样,同是流离失所之人,正因为如此,我们就是一家人,想不到大王突然有此征召。一直向西吧,按法令规定该杀;延迟军期吧,也是被杀;分配给契胡人吧,还是死,怎么办啦?”六镇人说:“只有反了。”神武说:“造反是最好的办法,但应推举一人主持。”众人都愿意听从神武指挥。神武又说:“我们乡下人难以约束,葛荣的下场大家看到过吧?虽拥众百万,无条令法律,结果便是自取灭亡。眼下大家推我为主,应当与以前有所区别,即不得欺侮汉人,不得触犯军令,死生均听任我安排才行,否则,就会被天下人耻笑。”众皆诺诺,死生听命。神武佯装无可奈何,次日,杀牛犒劳士卒,宣布攻讨尔朱兆的用意。封隆之进言说:“真是千载一时的好机会,天下所有人的大幸。”神武回答说:“讨伐盗贼,大顺民心;拯救时局,大功伟业。我虽不武,以死继之,哪敢推辞呢。”
六月,在信都举起义旗,但还没有公开背叛尔朱氏。到李元忠与高乾平定殷州,斩尔朱羽生头颅前来拜谒,神武捶胸道:“今天反叛定了!”于是便委元忠为殷州刺史。此时,军力猛增,乃上书揭发尔朱氏罪行,但世隆等人扣压上书没有向节闵帝禀告。八月,尔朱兆攻克殷州,李元忠逃到了神武驻地。孙腾认为朝廷隔绝,不临时立一天子,那么众望就无所归依。十月,奉章武王融之子渤海太守朗为皇帝,年号中兴,这便是魏朝的废帝。时度律、仲远军队驻扎在阳平,尔朱兆与他们见了面。神武采用窦泰计策,实行反间,度律、仲远不战而返,神武便在广阿打败了尔朱兆。十一月,进攻邺城,相州刺史刘诞闭城固守,神武命令兵士堆起土山,挖掘地道,并到处立起大木柱,之后一齐点火焚烧这些柱子,城陷到了地下。这时麻祥为汤阴县令,神武喊他“麻都”麻祥羞愧,逃走了。永熙元年(532)正月,攻克邺城,并占领了它。废帝晋升神武为大丞相、柱国大将军、太师。与此同时,青州树起义旗的大都督崔灵珍、大都督耿翔均派遣使者请求归附,行汾州刺史事刘贵弃城前来投降。闰三月,尔朱天光从长安,尔朱兆由并州,度律从洛阳,仲远由东都出发会合邺城,号称兵众二十万,依洹水布置战阵,节闵帝委派长孙承业为大行台总督其事。神武命令封隆之固守邺城,自己率兵离邺屯驻紫陌。此时神武拥有的战马不足二千,步兵不满三万,众寡悬殊。神武在韩陵布置圆形军阵,连结牛驴阻塞了归路,使得将士都有了决一死战的斗志,四面八方攻打敌人。尔朱兆谴责神武叛逆。神武称:“戮力同心,为的是共同辅佐王室,如今皇帝在哪?”尔朱兆答:“永安皇帝冤杀天柱,我只不过是替他报仇罢了。”神武道:“我往昔亲耳聆听了天柱的大计,当时你就站在门前,难道能讲不反的话吗?再说君杀臣,有何仇可报,今天我们就断绝关系吧。”言毕,双方交战,神武大胜。尔朱兆对着慕容绍宗拍打着胸脯说:“我不听您的话,终于得到了如此下场。”说着就想轻装逃跑。绍宗将前军旗帜移后,吹响鼓角,收聚残兵,组成军队的阵势向西撤去。高季式率七骑追击,翻过野马岗,碰到了尔朱兆。高昂在很高的地方都看不到季式,哭泣着说:“我失掉了亲弟弟啦!”夜很深了,季式才回来,血流满衣。斛斯椿兼程而行先占据了河桥。当初,即普泰元年(531)十月,岁星、荧惑、镇星、太白相聚于觜,亮灿灿的。太史占卜后说:“这是王者兴起之兆。”此时神武从信都起军,到这个时候便打败了尔朱兆等部。四月,斛斯椿捉住天光、度律解送到了神武那里。长孙承业派遣都督贾显智、张欢入洛阳,活捉了世隆、彦伯,并开刀问斩。尔朱兆逃到并州。仲远跑往梁州,很快就死在了这里。是时凶暴已除,朝廷喜悦。当初战事未起的前一个月,章武人张绍半夜里突然被几位骑士挟持翻过城墙,来到一大将军面前。大将军命令张绍做向导,领兵往邺,为的是辅佐朝廷除去残贼。张绍回过头来看时,士卒极多,但却异常整肃没有一点声响。快到邺城了,才放他回家。到交战这天,尔朱氏军人见军阵外神武的骑兵步卒四面逼近,大概是得到了天神的帮助。
紧接着神武就进入了洛阳,废掉节闵帝和中兴主而立孝武。孝武即位,授神武大丞相、天柱大将军、太师、世袭定州刺史,增加封地连前累计十五万户。神武不接受天柱大将军之职,还请求减少五万封户。过了几天,还邺,魏帝在乾脯山摆设宴席,同神武手拉手相互道别。
七月,神武率部北伐尔朱兆。封隆之说:“侍中斛斯椿、贺拔胜、贾显智等人以前服侍尔朱氏,都是忘恩负义之徒,现在住在京城,受宠遇,一定会制造事端的。”神武很是赞同这一看法,押解天光、度律来京师后,就处死了他们。于是神武从滏口进入。尔朱兆大肆抢掠晋阳,北保秀容,平定并州。神武认为晋阳四周阻塞,就将大丞相府安置到了这里。尔朱兆已经到了秀容,分兵把守险要之处,时常派兵出去抢劫骚扰。神武公开宣言讨伐,却是干打雷不下雨,因此尔朱兆便放松了警惕。神武估摸到新年时尔朱兆要宴会,就派遣窦泰率领最精锐的骑兵急奔秀容,一天一夜跑了三百多里,接着神武又派出主力紧随其后。二年正月,窦泰悄悄地进到了尔朱兆的庭院之中。尔朱兆的兵士由于大吃猛喝十分庸懒,猛然看到窦泰的骑兵,都惊慌而逃,追赶到赤洪岭,打垮了他们。尔朱兆上吊自杀,神武亲临丧场,用厚礼安葬。慕容绍宗带着尔朱荣的妻、子和剩余的部众固守乌突城,投降后,神武认为他有义,待其十分厚重。
神武占据洛阳后,尔朱仲远部下都督桥宁、张子期从滑台赶来归附,神武认为他们助纣为虐,而且反复无常,就杀掉了他们。斛斯椿因此内心恐惧,就与南阳王宝炬及武卫将军元毗、魏光、王思政在魏帝面前诬陷神武。舍人元士弼又奏报神武接受诏书时极不恭敬。先前魏帝对贺拔岳有疑心。孝明帝时,洛阳城中两拔互相搏击,谣言说:“铜拔打铁拔,元家将败亡。”好事者附会二拔为拓拔、贺拔,讲的是这两家都即将衰败的征兆。此时司空高乾密函告知神武,称魏帝贰心,神武就将此密信上呈。魏帝就杀了高乾,又遣东徐州刺史潘绍业密令长乐太守庞苍鹰杀掉高乾的弟弟昂。昂早就听到兄遇害的消息,用长矛刺柱,在路旁埋伏壮士活捉了潘绍业,并从其身上搜到了魏帝的敕书,然后前来投奔神武。神武抱着高乾的头颅,哭着说:“天子冤枉杀了我们的司空!”马上让人用白武幡安慰其家属。这时高乾的另一个弟弟高慎在光州,为政严猛,又纵容部下巧取豪夺,魏帝撤了他的职。高慎听到这不好的消息,打算逃亡梁州。其部将劝慰道:“您有大功于国,不一定受株连。”高慎就穿着破衣推着小车回到渤海。路上遇到使者,就跟着投奔了神武。于是魏帝与神武有了隔阂。
阿至罗人正光年前常对魏称臣,自从朝廷多事,都叛变了。神武派遣使者招纳,他们就归顺了。先前,魏帝诏令平定贼寇后,罢除行台。到那个时候,异族纷纷归附,又授神武大行台,给予相机处事的权力。神武送给异族人粮食衣服,旁人认为这是浪费,得不到益处,神武不听,一如既往地进行安抚。酋帅吐陈等人感恩不尽,都愿意听从指挥,救曹泥,取万俟受洛干,起了极大作用。河西费也头人纥豆陵伊利盘踞于河池,拥众恃险,神武虽多次派遣长史侯景招附,但他却不顺从。