皇帝詔命既下，上下官員雖然心中不願，卻也沒有人再敢反對，隻好遵旨照辦。經過了幾天的時間，所有行裝俱已打點完畢。劉邦與太公、後妃、太子等各自登車，儀仗隊排列成陣，文武百官及護衛軍隊簇擁聖駕，就浩浩蕩蕩向西進發。
大隊人馬行了許多時日，方才來到櫟陽，蕭何便前來迎駕。安頓下來後，劉邦把蕭何召來，單獨相見。對他說了遷都一事，蕭何道：“秦關雄固，的確是最佳之選。但自項羽入關以後，鹹陽的宮室都被他燒毀，縱使有幾間屋宇剩下，也是殘缺不全。以臣看來，陛下隻能暫居櫟陽，等臣重修宮室，盡快竣工，方好讓陛下遷居入住。”劉邦便聽從蕭何之言，在櫟陽停留，委派蕭何到鹹陽，監修宮闕。
正當劉邦在櫟陽等候宮室建成之時，突然傳來急報，說燕王臧荼反了。劉邦不由怒道：“這個臧荼本來就無尺寸之功，因為他肯投降，才讓他留任燕王，他不知感恩，反而敢來造反？”盛怒之下，劉邦便決定親征。當即點齊人馬，星夜出發，殺入燕境。
這一次出擊，正是迅雷不及掩耳，臧荼那邊還沒有部署好，漢軍便已殺到，直如神兵天降。本來燕地百姓都不想再受戰亂之苦，因此漢兵一到，百姓紛紛迎接。漢軍勢如破竹，直逼燕都。臧荼唯有率領部兵，主動出擊，在薊城外與漢軍接戰。可是燕兵都無心戀戰，雙方一交手，燕軍便潰，臧荼隻能敗退回城。漢軍將薊城團團圍住，城中軍民皆不願出力，結果隻支撐了幾天，薊城就被攻破，臧荼逃走不及被擒，其子臧衍則從北門逃出，投奔匈奴而去。大軍進城之後，劉邦將臧荼梟首示眾，盡服燕地人心，叛亂順利告平。
叛亂雖平，燕王必須重立，劉邦就想立一心腹之人來當此重任。劉邦孰意於同鄉故友盧綰，因此人與他同日出生，又是同學，長大後同遊之玩伴。從劉邦在沛縣起義以來，盧綰一直跟從，現官居太尉，能自由出入劉邦的臥室，不必避嫌。劉邦對他的優待，連蕭何、曹參也不能比。不過盧綰的才幹平庸，立的軍功也不多，如果不是劉邦一心要任用親近之人，大臣們也不會把他放在眼內。現在從劉邦身邊的侍從那兒得到風聲，知劉邦有意讓盧綰任燕王，於是大臣們紛紛上疏推薦。這正是劉邦所想見到的，便接納大臣推薦，立盧綰為燕王。把燕地情況都交待清楚後，劉邦就率大軍啟程西還。
哪知大軍還沒有回到關中，就又有消息傳來，說是潁川侯利幾也反了。利幾是昔日的陳縣縣令，項羽敗亡，他舉城降漢，封為潁川侯。但利幾終是非真心降順，所以很快又造反了。不過潁川隻是一個小城，大軍壓境，瞬即陷落，利幾也被人頭落地。
攻滅了利幾之後，劉邦凱旋回到洛陽，已是新年時分，於是就在洛陽大宴群臣。這場宴會十分痛快，劉邦喝個酩酊大醉。第二天到午後才起床，卻見一名侍臣匆匆走了進來，呈上一份奏疏。劉邦翻開一看，原來是一份密報，說故楚大將鍾離昩現正投在楚王韓信府中。劉邦看到此報，大吃一驚，心中生疑，當即命一近臣為使，齎詔到楚地，要韓信交出鍾離昩。
韓信收留鍾離昩，乃是念在大家是楚人，而且韓信在楚任事時，也受鍾離昩幫助，所以韓信才把他留於府中。使者到來，把劉邦的詔書呈上，韓信看完此詔，沉默了片刻，然後就對使者說：“陛下的消息一定有誤，我府中豈會有項氏舊部留居。請回複陛下，鍾離昩的確不在此間，但我會加強防範，一旦發現其行蹤，必將他緝拿，獻與陛下。”使者就記下韓信之言，回去照直答複。
雖然韓信說沒有，但劉邦對韓信已經失去信任，處處對他防範，當然不會盡信他的回答。他派出精幹的吏員前往楚地，仔細查探。到了下邳，這些吏員明察暗訪，探聽虛實。正好遇著韓信出巡，其車馬儀仗，加上護衛人馬，足有數千人，聲勢浩大，威風極盛。這些吏員覺得韓信此舉分明是起了異心，當即趕回去報知劉邦。
劉邦因為韓信是“三絕星”之一，加上他當初攻齊時害死酈生、擁兵脅封等，已經深深種下對韓信的疑忌之根，現在聽了吏員回複，就確信有叛意無誤。於是，劉邦召集眾將來，問他們可有對付韓信之法，眾將皆齊聲道：“豎子造反，隻要天兵一至，便可將他擒住，陛下放心！”
劉邦聽了，頓時沉默不語，他知道這裏的人沒有一個是韓信對手，隻會空言大話。眾將見皇帝不出聲，頓時僵住，不知所以，隻好陸續退出。眾將退出時，正遇陳平來見，便拉住陳平，說皇帝心中正在苦惱，陳平忙問何事，大家將韓信有反叛之意的事告知，陳平才明白過來，並且點了點頭，就走進宮裏。
劉邦苦惱之際，見陳平來了，連忙讓他近前，陳平趨至劉邦跟前道：“參見陛下。”
劉邦道：“你來得正好，快為我籌謀對付韓信之法。”
陳平道：“臣剛才進來的時候，已經聽大家說過韓信之事。不過此事不能著急，還要慢慢地去籌劃，才能周全。”
劉邦卻道：“這事怎麼能緩？你快為朕設計吧。”