漢二年（前205）三月，經過了半年多的精心準備，漢王劉邦率領三十餘萬漢軍主力從臨晉關東渡黃河，魏王豹投降，並派兵追隨劉邦東征。漢軍之所以所向披靡，關鍵在於劉邦的人望。
不久，漢軍又在韓信的率領下攻占河內（在今河南北部），俘虜了殷王司馬卬，並置其地為河內郡。此時漢軍人數占據優勢，所以攻城略地不費吹灰之力，兵力越多，使得就越順手。也就是在這個時候，劉邦得到了他此生中的另一位重要謀士——即之前與韓信一同勸阻項羽不要殺降的陳平。陳平其人最善奇謀，他同韓信一樣是從項羽那裏逃亡出來的，不過他是畏罪潛逃。
陳平本來是項羽手下的一名都尉，奉命率部配合聯軍殷王與漢軍作戰，結果失利，因為將兵攻伐本就不是他的所長。當他麵見劉邦時，劉邦非常欣賞他的才能，當即就任命他為漢軍都尉，並且還放心大膽地讓他做自己的參乘扈從官，並典護軍以監督各軍的舉動。
別看劉邦平時不大著調，可是在很多大事上往往不乏魄力，不可作尋常觀，韓信也有些揣摩不透他。諸將對重用陳平一事提出異議，劉邦反而更加信任陳平。出身下層的劉邦曉得同樣出身的陳平（甚至包括韓信等人）心裏究竟想什麽，真正需要什麽，這就是劉邦比項羽的高明之處。接著，漢軍又從平陰津南渡黃河，到達洛陽新城，一路進展非常順利。在這裏，劉邦接受了一位長者（三老）董公的建議，為義帝舉行了隆重的葬禮，借以收取天下人心。劉邦袒而大哭，哀臨三日，並向天下諸侯發布了討伐項羽的文告。當漢使者到達趙國時，主政的陳餘要求劉邦殺死張耳，否則不會出兵。當時趙國的實力相當雄厚，漢方應當竭力爭取他們的援助。於是劉邦找了一個酷似張耳的替死鬼，陳餘果然上當。