劉裕納其言。由於忌憚劉裕，桓玄便於九月派其從兄衛將軍桓謙試探劉裕，桓謙屏退眾人，問劉裕：“楚王勳德隆重，四海歸懷。朝廷之情，鹹謂宜有揖讓，卿意以為何如？”劉裕假從其言，回答說：“楚王，宣武之子，勳德蓋世。晉室微弱，民望久移，乘運禪代，有何不可！”桓謙聞後大喜道：“卿謂可爾，便當是真可爾”(《宋書。武帝本紀》)。十二月，桓玄逼晉安帝司馬德宗讓位於己，國號楚。桓玄稱帝後，“禍難屢構，幹戈不戢，百姓厭之，思歸一統”(《晉書。桓玄傳》)。劉裕看清了局勢，與劉毅、何無忌等共謀反桓之事。從此，拉開了平定桓玄之亂的序幕。元興三年(404年)二月，劉裕隨徐、兗二州刺史，安成王桓修入朝。桓玄見到劉裕，對司徒王謐說：“昨見劉裕，風骨不恒，蓋人傑也。”每次遊玩集會，都對劉裕態度優禮有加，贈賜甚厚。桓玄妻劉氏有智鑒，對桓玄說：“劉裕龍行虎步，視瞻不凡，恐不為人下，宜蚤為其所。”桓玄說：“我方欲平蕩中原，非劉裕莫可付以大事。關隴平定，然後當別議之耳。”於是下詔說：“劉裕以寡製眾，屢摧妖鋒，泛海窮追，十殄其八。諸將力戰，多被重創。自元帥以下至於將士，並宜論賞，以敘勳烈”(《宋書。武帝本紀》)。桓玄以為用這種懷柔政策可以打消劉裕的不滿情緒，但劉裕卻暗中作了大量準備工作，加緊了起兵的步伐。不久，劉裕以舊傷複發為由，與何無忌同船而回，密謀興複晉室。於是劉裕與其弟劉道規、何無忌、沛郡人劉毅、平昌人孟昶、任城人魏詠之、高平人檀憑之、琅邪人諸葛長民、太原人王元德、隴西人辛扈興、東莞人童厚之等共同謀劃起兵。時桓修弟桓弘為征虜將軍、青州刺史，鎮守廣陵，劉道規為桓弘中兵參軍，孟昶為主簿。劉裕暗中派劉毅至江北，起兵後與二人共殺桓弘；諸葛長民為豫州刺史刁逵左軍府參軍，劉裕令其殺刁逵，占據曆陽；王元德、辛扈興和童厚之則在京城活動，以為內應。是月，劉裕以遊獵為由，與何無忌等人相聚，共有百餘人。
第二天清晨，京口(今江蘇鎮江)城開，劉裕與何無忌等襲殺桓修。劉毅與孟昶等人於廣陵(今江蘇揚州市)攻殺桓弘。劉裕被推為盟主。傳檄文於京城：“夫治亂相因，理不常泰，狡焉肆虐，或值聖明。自我大晉，陽九屢構。隆安以來，難結皇室。忠臣碎於虎口，貞良弊於豺狼。逆臣桓玄，陵虐人鬼，阻兵荊郢，肆暴都邑。天未亡難，凶力繁興，逾年之間，遂傾皇祚。主上播越，流幸非所；神器沉淪，七廟毀墜。夏後之罹浞、豷，有漢之遭莽、卓，方之於玄，未足為喻。自玄篡逆，於今曆年，亢旱彌時，民無生氣。加以士庶疲於轉輸，文武困於造築，父子乖離，室家分散，豈唯《大東》有杼軸之悲，《摽梅》有傾筐之怨而已哉！仰觀天文，俯察人事，此而能久，孰有可亡！凡在有心，誰不扼腕。諱等所以叩心泣血，不遑啟處者也。是故夕寐宵興，援獎忠烈，潛構崎嶇，險過履虎。輔國將軍劉毅、廣武將軍何無忌、鎮北主簿孟昶、兗州主簿魏詠之、寧遠將軍劉道規、龍驤將軍劉籓、振威將軍檀憑之等，忠烈斷金，精貫白日，荷戈奮袂，誌在畢命。益州刺史毛璩，萬裏齊契，掃定荊楚。江州刺史郭昶之，奉迎主上，宮於尋陽。鎮北參軍王元德等，並率部曲，保據石頭。揚武將軍諸葛長民，收集義士，已據曆陽。征虜參軍庾賾之等，潛相連結，以為內應。同力協規，所在蜂起，即日斬偽徐州刺史安城王修、青州刺史弘首。義眾既集，文武爭先，鹹謂不有一統，則事無以輯。諱辭不獲已，遂總軍要。庶上憑祖宗之靈，下罄義夫之力，翦馘逋逆，蕩清京輦。公侯諸君，或世樹忠貞，或身荷爵寵，而並俯眉猾豎，自效莫由，顧瞻周道，寧不吊乎！今日之舉，良其會也。諱以虛薄，才非古人，接勢於已替之機，受任於既頹之運。丹誠未宣，感慨憤躍，望霄漢以永懷，眄山川以增厲。授檄之日，神馳賊廷”(《宋書。武帝本紀》)。
劉裕以孟昶鎮守京口，自率部眾1700餘人，進駐竹裏(今江蘇句容北)。劉裕部初克建康時，桓修司馬刁弘率文武佐吏前來救援。劉裕登上城樓對他說：“郭江州已奉乘輿反正於尋陽，我等並被密詔，誅除逆黨，同會今日。賊玄之首，已當梟於大航矣。諸君非大晉之臣乎，今來欲何為”(《宋書。武帝本紀》)？刁弘被劉裕唬住，隻好收眾而退。不久劉毅率部眾趕到，劉裕急命他殺了刁弘。劉毅的兄弟劉邁原來也在建康。劉裕起兵討桓玄後，曾派遣同謀周安穆前去通報劉邁，要他為內應。劉邁為人膽小怕事，他表麵敷衍周安穆，內心卻不敢應允。周安穆看破了他的心事，心中懊悔，害怕事情會因此泄露，於是急忙趕回報告劉裕。這時，桓玄任命劉邁為竟陵太守。劉邁不知如何是好，準備船隻走馬赴任。一日夜，劉邁接到了一封桓玄給他的信。信中問道“北府人情雲何？卿近見劉諱何所道”(《宋書。武帝本紀》)？劉邁閱信後驚恐萬分，以為桓玄已經知道劉裕的陰謀了。第二天一早就把事情全盤托出。桓玄大驚，封劉邁為重安侯，既而一想，劉邁不抓住周安穆，使周安穆得以逃出，於是又把劉邁給殺死。桓玄以揚州刺史桓謙為征討大都督(參見覆舟山之戰)。桓謙等主張迎擊劉裕，桓玄則認為：“不然。彼兵速銳，計出萬死。若行遣水軍，不足相抗；如有蹉跌，則彼氣成而吾事敗矣！不如屯大眾於覆舟山以待之。彼空行二百裏，無所措手，銳氣已挫，既至，忽見大軍，必驚懼駭愕。我案兵堅陣，勿與交鋒。彼求戰不得，自然散走。此計之上也”(《宋書。武帝本紀》)。桓謙力爭出擊，桓玄乃遣頓丘太守吳甫之、右衛將軍皇甫敷相繼自建康北攻京口。桓玄自聞劉裕起兵，甚為憂懼，有人勸慰他說：“劉裕等眾力甚弱，豈辦之有成，陛下何慮之甚！”桓玄說：“劉裕足為一世之雄，劉毅家無擔石之儲，摴蒲一擲百萬；何無忌，劉牢之甥，酷似其舅。共舉大事，何謂無成”(《宋書。武帝本紀》)。
三月，劉裕與吳甫之在江乘(今江蘇句容北)遭遇。吳甫之是桓玄驍將，其兵甚銳。劉裕手執長刀，大呼而衝，所向披靡，斬吳甫之。劉裕追至羅落橋(今南京東北)。皇甫敷率數千人迎戰劉裕，寧遠將軍檀憑之與劉裕各率一部，檀憑之戰死，其眾潰退。而劉裕則進戰彌厲，奮勇無比，斬皇甫敷。桓玄聞二將戰死，大懼，再遣桓謙及遊擊將軍何澹之屯兵東陵(覆舟山東北)，侍中、後將軍卞範之駐軍覆舟山以西，合計兵力二萬人。劉裕令部隊飽食後，棄餘糧，輕裝進至覆舟山以東，派老弱登山，張旗幟為疑兵，迷惑桓玄。桓玄急調武衛將軍庾賾之率精兵出援各軍。醒謙的士兵多為北府人，素畏伏劉裕，所以莫有鬥誌。劉裕與劉毅等將軍隊分為數隊，突擊桓謙軍。劉裕身先士卒，將士無不死戰，以一當百。時值東北風急，劉裕借風縱火，“鼓噪之音震京邑”(《宋書。武帝本紀》)，桓謙大敗。桓玄已無意再戰，率其子侄乘船沿江南下。劉裕率軍進入建康(今南京)，並遣諸將追擊桓玄。劉裕入建康後，屯石頭城，立留台官，焚桓溫神主於宣陽門外，重立晉新主在太廟中，以示自己是東晉的救世主。並誅殺桓氏宗族。桓玄司徒王謐與眾人推劉裕領揚州，劉裕心不在此，辭不肯受。乃以王謐為侍中、領司徒、揚州刺史、錄尚書事；王謐推裕為使持節、都督揚、徐、兗、豫、青、冀、幽、並八州諸軍事、徐州刺史；劉毅為青州刺史；何無忌為琅邪內史；孟昶為丹陽尹；劉道規為義昌太守。劉裕一下重兵在握，這才答應下來。桓玄當權時，接下來的是晉朝廷留下來的爛攤子，史稱當時“百司縱弛，桓玄雖欲厘整，而眾莫從之”(《宋書。武帝本紀》)。