經天子首肯後，京中便開始緊鑼密鼓地準備此事。賞賜的金銀次日就發過了，隴右三鎮得知並無重任，其實也樂得輕鬆，並無異議。至少從此時來看，涼州上下還是一片和諧。唯有此時大雪不停，出兵的時日難免遭到拖延，一直到冬月十三，冰雪稍小，呂布才重新踏上征程。
出發之前，賈詡特意問呂布道：“冬日攻城極難，不知將軍可有把握？”
呂布徑直答說：“河東守卒匪多，戰意低沮，有何憂慮？正常蟻附攻城，足可下之。”
賈詡卻搖首道：“若是如此攻城，將軍無疑是捨己之短，攻敵之長，恐怕難有作爲。”
呂布反問道：“那依文和之見，莫非是有破城的法子咯？”
賈詡笑道：“破城的法子其實也沒有，但不戰獲城的法子倒還有。”
他隨即說道：“如若蒲坂之敵堅守不出，將軍可舍其不顧，繼續北走。抄掠於鄉野之間，因糧於安邑、臨汾等地。所遇的邑居村落全部燒燬，有出奔逃命的軍民並皆殺死。四處多張旗幟，使敵人不知我虛實。而後再放出消息，敢據守不降者，必以屠城爲懲。賊軍聞訊，軍心必然潰散，要麼出城決戰，要麼棄城而逃，那河東便是囊中之物了。”
呂布聽罷，不由笑道：“文和說得在理，不過依我看，倒也不必如此麻煩，若是我攻城不下，再用此計不遲。”
說罷，事不宜遲，呂布當即領兵過渭橋，打算經高陵、萬年而至臨晉。經過高陵時，他看到當年與涼軍廝殺的戰場，心中唏噓不已，指着凍結的渭水對張遼說：“可惜當年上黨隨我入雒陽的弟兄，如今所剩已不足千人，且大多都葬身在此地了。如今縱得富貴，又能與誰人論說呢？”
張遼則說：“只要將軍能夠善始善終，助陛下成就大業，那我上黨武人的名聲，想必也能如漁陽突騎般流芳百世吧。”
呂布微微頷首，說道：“來都來了，也不能當就此路過。當年冠軍侯大敗匈奴，在河西犒賞將士，便將美酒倒入泉水中與三軍共飲。今日我緬懷袍澤，也當如此。”
說罷，便取出兩壇天子御賜的襄陽黃酒，令人敲碎河冰，將酒水灑在渭水之中。他在心中默唸道：“諸位袍澤，昔日你們葬身水中，是我呂布無能。可若你們死後有靈，能品到這江水醞釀的黃酒，請你們保佑，助我成就不世功績，名揚萬古！”
當夜，他們就在渭水邊築營歇息，又叫來當地的五名亭長。說要打聽一下涼軍入京後，關中民衆的議論，以及周遭最近的情形。這些亭長聽得是新任大將軍相詔，不敢怠慢，就都跪坐在呂布帳中央，呂布問一句，他們就答一句，也不敢擡頭去看。
不過說到底，也不過是呂布想聽些恭維話罷了。幾個亭長都非常識趣，呂布問民意如何，他們就說了些二賊無道、大將軍順時應命，百姓聞之若逢寒霖的言語，聽得呂布心中大悅，只是又不願顯露出來，便不斷撫頜掩飾笑意。
還是高順詢問他們，最近周遭有無異動時。一人說，他聽了消息，這兩日在頻陽一帶，似有馬匪流竄，但也沒有傷人，十分怪異。
高順聽罷極爲重視，便與呂布討論，會否是晉陽來的騎軍？呂布則不以爲然，說冬日裏有馬匪，那是自然之事，如今長安下城不過一旬，晉陽哪裏來得援軍？不必如此憂心。又是又問那人，可知有多少馬匪？那人回答不知，呂布便愈發不放在心上。
如此到第二日，呂布率軍離開高陵，過萬年而到蓮勺，直接踏馬穿過凍結的洛水，繼而抵達臨晉城下。此時他率軍出戰的消息已爲河東知曉，警訓同時向晉陽與雒陽快速飛奔。不過這個時候呂布並不害怕被發現了，畢竟他要的不只是快速行軍，鎮撫關中各郡縣，也是他的目的之一。故而雖然是騎馬奔襲，沿路他大張旗鼓，高掛大將軍旌節，又令部下山呼討賊，沿路鄉亭聞之無不戰慄膽寒，都太息道：關中不過太平數年，孰料終又重啓戰亂。
待他們渡過河水西岸，已是冬月十七的早上。天上的雲層很淡，風很輕，太陽有光輝灑下，但是沒有溫度，衆人漫步在雪中，只覺天地白得更加燦爛，但也更加冷漠了。
雖然明知不利，然而呂布卻仍要強攻。當日，他下令軍士，打算自城南、城北、城西三面大起土山，進行圍攻。同時戰鼓徹夜不休，城內更無一刻安寧。
只是攻城之初，呂布便遇到了極大困難。冬日裏土地板結僵硬，不僅填挖費時，挖出的泥土還硬脆成塊，若不再派人碾壓搗碎，根本難以填山。如此情形下，呂布第一日連起土山兩次，皆倒塌。而在城上弓矢箭雨之下，涼卒們雖身穿甲冑，並無大損，可無法還擊徒增傷患的前提下，士氣無可奈何地也隨之低沮。
呂布見狀，當夜擄來當地千餘百姓，花了整整兩日督造雲梯衝車，事後得雲梯百餘架，呂布再驅使百姓在前，向蒲坂架梯攻城。百姓本來害怕至極，但受刀劍相逼，不得已擡着雲梯躑躅向前，在城上的人看來，他們搬着比自己旁大許多的雲梯，真如螻蟻一般。其中有些人還是當地郡兵的鄉卒，守軍實在不忍下殺手，還是陳登嚴聲怒斥，才把備好的石塊砸到牆下。
只是到底慢了少許，幾臺雲梯一架上，涼軍們便帶着鐵兜鍪，用鐵甲頂着箭矢攀爬而上。在他們想來，只要能爬上城牆與守軍肉搏，這些河東的富家子弟定然難以招架，奪城也不過頃刻間。但令他們意想不到的是，剛爬到牆頭，探出雲梯的雙手抓過去，全是滑溜溜的冰層，全然無處用力，守軍們就趁他們無所適從的時候，用事先準備好的大棒，不斷地毆擊涼軍，涼軍無力抵抗，要麼被大棒打落城下，要麼只能識趣地自行退下。
至於在城下的衝車，守軍們也都反覆潑過水，導致城門前也結了一層厚厚的冰。冰層是一個帶幅度的仰坡，涼軍們推着衝車往前，卻發現全然推不上去，只得又令鄉民在城門前鑿冰，但如此一來，在冰層徹底鑿完前，衝車是推不進去了。
如此又過了兩天，呂布不得已停止了攻城。他將軍中的將佐都叫到一起，繼續商議如何破城的法子。但討論了半日，還是莫衷一是。
張遼勸諫呂布說：“這幾日攻城，可見蒲坂並無多少守軍，並不足爲患。何必在此處空耗？大將軍既然要全取河東，便不當拘泥於一隅，而要放眼全局纔是。何不暫棄此城，直取平陽。平陽牆矮，我軍又出其不意，必能一戰而克！”
呂布聽聞，頓時記起臨行前賈詡的計策。他也知戰事不容兒戲，思忖片刻，便頷首說道：“倒也不必前往平陽，我等只要奪下臨汾，便也不怕晉陽的援軍了。”
說罷，呂布當即整頓將士，棄蒲坂於不顧，繼續往東。當夜，他們趕到了鹽池，在池邊停下來休息。這個時候，突然北邊的遠處冒起了火光。騎兵們本來都下了馬了，又都連忙重新騎上去。
有人說，是不是敵軍的斥候來了？另外有人就說，不可能是斥候，趕在夜間舉火行軍的，人數肯定不在少數。
正在猜疑間，漸漸地，前方的火光越來越多，而且慢慢蔓延開來，一直到北邊完全連成了一條線，就像一條火龍一般。有人站在馬上，朝火光閃耀處張望，除了一股股的雪氣與塵埃像霧氣一樣從樹林間騰空而起，別的什麼也看不見。
人們議論道：“到底有多少人過來了？好像很多似的。”不一會，鳴鼓和軍士嘈雜的聲音也傳了過來。聲音越來越大，就像黃河的波濤洶涌撲向岸邊的岩石。
有些人慌了，議論說：“是不是被包圍了，還是趕快衝出去吧！”
然而呂布卻強令他們噤聲，他看着對面踟躕的火龍笑說道：“這些小賊還不敢妄動，我們又何必後退？”
他側耳又聽了一會，辨析敵軍的口音，最終笑道：“看來來的是匈奴的騎軍，不值一提！正是我立威的時候呢！”
他說得不錯，對面來的這萬餘騎士，正是陳羣自美稷請來的匈奴援軍。