魏普泰元年（531）二月，神武率軍駐紮信都，高乾、封隆之大開城門等候著，很快就占領了冀州。本月，爾朱度律廢元曄立節閔為皇帝，想羈縻住神武，三月，請求節閔封神武為渤海王，征召使其入朝覲見。神武推辭未去。四月癸已日，又加授神武東道大行台、第一鎮人酋長。龐蒼鷹從太原跑來投奔，神武任命他做行台郎，不久升任安州刺史。神武率眾挺進山東，養育兵士，修理武器，禁止侵掠，更贏得了百姓的歸附。神武偽造書信，說爾朱兆擬將六鎮人分配給契胡為部曲，因此使這些人十分的愁苦怨恨。又製成並州符節，征兵討伐步落稽。發動萬人，準備派遣出去，孫騰、尉景假意請求延緩五天動身，這樣反複了幾次。神武親自送到郊外，流著淚向六鎮人道別，人們都十分悲痛，哭聲震天。神武開導說：“我和你們一樣，同是流離失所之人，正因為如此，我們就是一家人，想不到大王突然有此征召。一直向西吧，按法令規定該殺，延遲軍期吧，也是被殺，分配給契胡人吧，還是死，怎麼辦啦？”六鎮人說：“隻有反了。”神武說：“造反是最好的辦法，但應推舉一人主持。”眾人都願意聽從神武指揮。神武又說：“我們鄉下人難以約束，葛榮的下場大家看到過吧？雖擁眾百萬，無條令法律，結果便是自取滅亡。眼下大家推我為主，應當與以前有所區別，即不得欺侮漢人，不得觸犯軍令，死生均聽任我安排才行，否則，就會被天下人恥笑。”眾皆諾諾，死生聽命。神武佯裝無奈何。次日，殺牛犒勞士卒，宣布攻討爾朱兆的用意。封隆之進言說：“真是千載一時的好機會，天下所有人的大幸。”神武回答說：“討伐盜賊，大順民心；拯救時局，大功偉業。我雖不武，以死繼之，那敢推辭呢。”
六月庚子日，在信都舉起義旗，但還沒有公開背叛爾朱氏。到李元忠與高乾平定殷州，斬爾朱羽生頭顱前來拜謁，神武捶胸道：“今天反定了！”於是便委元忠為殷州刺史。此時，軍力猛增，乃上書揭發爾朱氏罪行，但世隆等人扣壓上書沒有向節閔帝稟告。八月，爾朱兆攻克殷州，李元忠逃到了神武駐地。孫騰認為朝廷隔絕，不臨時立一天子，那麼眾望就無所歸依。十月六日，奉章武王融之子渤海太守朗為皇帝，年號中興，這便是魏朝的廢帝。時度律、仲遠軍隊駐紮在陽平，爾朱兆與他們見了麵。神武采用竇泰計策，實行反間，度律、仲遠不戰而返，神武便在廣阿打敗了爾朱兆。十一月，進攻鄴城，相州刺史劉誕閉城固守，神武命令兵士堆起土山，挖掘地道，並到處立起大木柱，之後一齊點火焚燒這些柱子，城陷到了地下。這時麻祥為湯陰縣令，神武喊他“麻都”，麻祥羞愧，逃走了。永熙元年（532）正月十七，攻克鄴城，並占領了它。廢帝晉升神武為大丞相、柱國大將軍、太子太師。與此同時，在青州樹起義旗的大都督崔靈珍、大都督耿翔一齊派遣使者請求歸附，行汾州刺史事劉貴棄城並來投降。閏三月，爾朱天光從長安，爾朱兆由並州，度律從洛陽，仲遠由東都出發會集鄴城，號稱兵眾二十萬，依洹水布置戰陣，節閔帝委派長孫承業為大行台總督其事。神武命令封隆之固守鄴城，自己率兵離鄴屯駐紫陌。此時神武擁有的戰馬不足兩千，步兵不滿三萬，眾寡懸殊。神武在韓陵布置圓的軍陣，連結牛驢阻塞了歸路，使得將士都有了決一死戰的鬥誌，四麵八方攻打敵人。爾朱兆譴責神武叛逆。神武稱：“戮力同心，為的是共同輔佐王室，如今皇帝在哪？”爾朱兆答：“永安皇帝冤殺天柱，我隻不過是替他報仇罷了。”神武道：“我往昔親耳聆聽了天柱的大計，當時你就站在門前，難道能講不反的話嗎？再說君殺臣，有何仇可報？今天我們就斷絕關係吧。”言畢，雙方交戰，神武大勝。爾朱兆對著慕容紹宗拍打著胸脯說：“我不聽您的話，終於得到了如此下場。”說著就想輕裝逃跑。紹宗將前軍旗幟移後，吹響鼓角，收聚殘兵，組成軍隊的陣勢向西撤去。高季式率七騎追擊，翻過野馬崗，碰到了爾朱兆。高昂在很高的地方都看不到季式，哭泣著說：“我失掉了親弟弟啦！”夜很深了，季式才回來，血流滿衣。斛斯椿反道而行先占據了河橋。當初，即晉泰元年（531）十月，歲星、熒惑、鎮星、太白相聚於觜，亮慘慘的。太史占卜後說：“王者興起之兆。”此時神武從信都起軍，此時已打敗了爾朱兆等部。四月，斛斯椿捉住天光、度律解送到了神武那裏。長孫承業派遣都督賈顯智、張歡入洛陽，活捉了世隆、彥伯，並開刀問斬。爾朱兆逃到並州。仲遠跑往梁州，不久就死在了這裏。是時凶暴已除，朝廷喜悅。當初戰事未起的前一個月，章武人張紹半夜裏突然被幾位騎士挾持翻過城牆，來到一大將軍麵前。大將軍命令張紹做向導，領兵往鄴，為的是輔佐朝廷除去殘賊。張紹回過頭來看時，士卒極多，但卻異常整肅沒有絲毫聲響。快到鄴城了，才放他回家。到交戰這天，爾朱氏軍人見軍陣外神武的騎兵步卒四麵逼近，大概是得到了天神的幫助。
緊接著神武就進入了洛陽，廢掉節閔帝和中興主而立孝武。孝武即位，授神武大丞相、天柱大將軍、太子太師、世襲定州刺史，增加封地連前累計十五萬戶。神武不接受天柱大將軍之職，並請求減少五萬封戶。還鄴，魏帝在乾脯山擺設告別宴席，同神武手拉手相互道別。七月壬寅日，神武率部北伐爾朱兆。封隆之說：“侍中斛斯椿、賀拔勝、賈顯智等人以前服侍爾朱氏，都是忘恩負義之徒，現在住在京城，受寵遇，一定會製造事端的。”神武很是讚同這一看法，押解天光、度律來京師後，予以處死。於是神武從滏口進入。爾朱兆大肆搶掠晉陽，北保秀容。平定並州。神武認為晉陽四周阻塞，就將大丞相府安置到了這裏。爾朱兆已經到了秀容，分兵把守險要之處，時常派兵騷擾。神武宣言討伐，卻是幹打雷不下雨，因此爾朱兆放鬆警惕。神武估摸到新年時爾朱兆要宴會，就派遣竇泰率領最精銳的騎兵急奔秀容，一天一夜跑了三百多裏，接著神武又派出主力緊隨其後。二年正月，竇泰悄悄地進到了爾朱兆的庭院之中。爾朱氏的兵士十分的慵懶，猛然看到竇泰的騎兵，都驚慌而逃，追趕到赤洪嶺，打垮了他們。爾朱兆上吊自殺，神武親臨喪場，用厚禮安葬。慕容紹宗帶著爾朱榮的妻、子和剩餘的部眾固守烏突城，投降後，神武認為他有義，待其十分的厚重。
神武占據洛陽後，爾朱仲遠部下都督橋寧、張子期從滑台趕來歸附，神武認為他們助桀為虐，而且反複無常，就殺掉了他們。斛斯椿因此內心恐懼，就與南陽王寶炬及武衛將軍元毗、魏光、王思政在魏帝麵前誣陷神武。舍人元士弼又奏報神武接受詔書時極不恭敬。先前魏帝對賀拔嶽有疑心。孝明帝時，洛陽城中兩拔互相搏擊，謠言說：“銅拔打鐵拔，元家世將敗亡。”好事者附會二拔為拓拔、賀拔，講的是這兩家都即將衰敗的征兆。此時司空高乾密函告知神武，稱魏帝貳心，神武就將此密信上呈。魏帝就殺了高乾，又遣東徐州刺史潘紹業密令長安太守龐蒼鷹殺掉高乾的弟弟昂，昂早就聽到兄遇害的消息，用長矛刺柱，在路旁埋伏壯士活捉了潘紹業，並從其身上搜到了魏帝敕書之後，前來投奔神武。神武抱著高乾的頭顱，哭著說：“天子冤殺了的司空！”馬上讓人用白武幡安慰其家屬。這時高乾的另一個弟弟高慎在光州，為政嚴猛，又縱容部下巧取豪奪，魏帝撤了他的職。高慎聽到消息，打算逃亡梁州。其部將勸慰道：“您有大功於國，不一定受株連。”高慎就穿著破衣推著小車回到渤海。路上遇到使者，就跟著投奔了神武。從此魏帝與神武有了隔閡。
阿至羅人正光以前常向魏稱臣，自從朝廷多事，都叛變了。神武派遣使者招納，他們就歸順了。先前，魏帝詔令平定賊寇後，罷除行台。到那個時候，異族紛紛歸附，又授神武大行台，給予相機處分的權力。神武送給異族人糧食衣服，旁人認為這是浪費，得不到益處，神武不聽，一如既往地進行安撫。酋帥吐陳等人感恩不盡，都願意聽從指揮，救曹泥，取萬俟受洛幹，起了極大作用。河西費也頭人紇豆陵伊利盤據河池，擁眾恃險，神武雖多次派遣使者招附，但他卻不順從。
天平元年（534）正月初九日，神武率軍前往河西，征討費也頭人紇豆陵伊利，取勝後，將其部眾遷往河西。
魏帝心中有異，時侍中封隆之私底下對孫騰說，隆之妻亡，魏帝想把妹妹嫁給他。孫騰不信，但內心生起嫉妒，就把這件事偷偷地告訴了斛斯椿。斛斯椿向魏帝做了報告。另外孫騰帶兵器進禁省，擅自殺了禦史。兩人同時逃走，投奔神武而來，向神武訴說魏帝在自己麵前毆打舍人梁續，光祿少卿元子幹捋袖伸臂跑來幫忙，並對孫騰說：“告訴你的高王，元家兒拳就這個樣子。”領軍婁昭托病回到晉陽。魏帝就讓斛斯椿兼任領軍，分別安排諸將以及河南、關西等地刺史。華山王鷙在徐州，神武派邸珍奪走了他的鑰匙。建州刺史韓賢、濟州刺史蔡俊協同神武舉義，魏帝對他們極其仇視。因此裁撤建州剝奪韓賢的要職，命令禦史中尉綦俊偵察蔡俊的犯罪事實，派開府賈顯智做濟州刺史，蔡俊不服，魏帝愈加惱怒。
五月魏帝下詔，稱要征討句吳，調集河南各州兵士，增加皇宮宿衛，派人守護河橋。六月初六日，魏帝秘密詔令神武：“宇文黑獺自從平定秦、隴之後，多有非分之求，倘有變動欺詐，務請策劃處理。不過，宇文氏的表、啟之中還沒有暴露出徹底的反叛之心，攻討之事不可匆匆決定，因此召集大臣，商議是否可行。都說以南伐為名，內外戒嚴，一來防備黑獺突然起事，二來可以威逼吳、楚。”此時魏帝準備攻打神武，正在調兵遣將，擔心神武懷疑，所以下詔解釋。神武則上書說：“荊州同蠻地相接，距畿服較近，關隴依仗邊遠，欲有逆謀。臣現在悄悄領兵三萬，擬從河東渡過黃河；又命令桓州刺史庫狄幹、瀛州刺史郭瓊、汾州刺史斛律金、前武衛將軍彭樂統兵四萬，從來違律渡河；派遣領軍將軍婁昭、相州刺史竇泰、前瀛州刺史堯雄、並州刺史高隆之率兵五萬，攻打荊州；調集冀州刺史尉景、原冀州刺史高敖曹、濟州刺史蔡俊、前侍中封隆之帶兵七萬、突騎五萬，進軍江左。都必須嚴格約束部眾，認真聽從指揮。”魏帝感覺有異，就拿出神武的上表，命令百官評議，希望能製止神武各路兵馬行動。神武也馬上召集在州郡的僚佐，請他們廣泛發表意見，再以表的形式上奏魏帝。依然用真誠的誓言表白自己的忠心：“臣遭小人離間，陛下萬一懷疑，其桀傲不馴之罪，就會像爾朱氏那樣受到誅討。臣如果不盡誠竭節，膽敢辜負陛下的話，那麼就使身受天禍，斷子絕孫。陛下如果相信臣的赤心，不興幹戈，就該將一二佞臣逐出朝廷。”二十日，魏帝選錄在京文武大臣的議論再次回答神武，讓舍人溫子升起草詔令，子升遲疑不決未敢動筆。帝坐在胡床上，變了臉色，拔出長劍威脅。子升這才拿起筆來。