1367年十月二十一日，吳王朱元璋正式任命徐達為征虜大將軍、常遇春為副將軍率師二十五萬北取中原。北伐大軍的第一個目標直指駐守山東的元兵。就在徐達等出師後的第二天，吳王朱元璋向中原地區齊魯、河洛、燕薊、秦晉一帶的人民發布了北伐檄文，宣布他派兵北伐的目的在於“逐胡虜，除暴亂，使民皆得其所，雪中國之恥”。這篇檄文的發布，對徐達所率北征將士獲取中原地區士民更廣泛的理解和支持，減少其進軍的阻力，發揮了一定的積極作用。
（一）平息沂州之亂
吳元年十月二十四日，大將軍徐達率軍到達淮安，遂派使者持信前往山東沂州（今山東臨沂市），招降在山東頗具影響的王宣及其子王信所領導的元朝地方武裝。王信收到徐達的招降書後，於二十八日遣使前來請降。但王信父子並不是真心投降，他們表麵上服從徐達調遣並派官員到徐達軍中犒勞將士，私下裏卻秘密到莒縣、密州募兵，為抵禦徐達做準備。十一月初十，王宣在所派犒軍官員回到沂州後，立即派兵乘夜襲擊徐達派駐沂州的將士徐唐臣等，徐唐臣乘亂逃回徐達軍營。徐達在得知王宣降而複叛的消息後，當即率軍直抵沂州城，紮營於北門外。起初，徐達仍想招降王宣，又派人前去勸說。王宣為了拖延時間，等待外出招募兵馬的兒子王信帶兵來援，仍故技重演，答應投降，卻仍是閉門拒戰。徐達大怒，指揮部隊猛攻沂州城，由於王信募兵未歸，王宣自知抵擋不住徐達的進攻，被迫在十二日向徐達投降，並交出了元朝廷授予的沂國公印等。隨後，徐達命令王宣修書一封，派部將前去招降其子王信。但王信拒不從命，並殺害了徐達派去的使者，與其兄王仁逃往山西。徐達因憤恨王宣的陰險狡詐、反複無常，且惱怒王宣之子殺害了其部將，於是下令處死了王宣。
（二）智取山東
徐達平息沂州之亂後不久，受其影響，元山東莒州、沂水、日照等地守將紛紛來降，並遵照吳王朱元璋的諭令命部將韓政扼守黃河要衝，以斷山東援兵。徐達親統大軍向益都（今山東益都市）方向推進。益都守將拒絕招降，徐達對部下說：“益都倚仗的是河上的援兵，現在我已派兵扼守黃河，斷絕了後路，他們還不知道自己已經成了甕中之鱉了。”於是下令填壩攻城。十一月二十九日，徐達攻陷益都，活捉了元益都守將。緊接著，徐達又乘勝出兵，連克壽光、臨淄、昌樂、高苑等縣及濰、膠、博興等州。此役，共計俘獲元軍將士一萬零五百餘人，馬騾一千六百餘匹，糧十八萬九千餘石。十二月初六，大將軍徐達兵至章丘，元守將右丞王成投降。次日，抵達濟南，留守的元將舉城投降，收複濟南，俘虜元軍二千八百五十五人，馬四百二十九匹。隨後徐達率兵進攻山東半島，元軍駐守萊陽、登州、寧海（今山東煙台市牟平區）的守將紛紛請降。在北伐軍的節節勝利聲中，朱元璋於1368年正月在應天登基稱帝，建國號為大明，建元洪武。徐達被封為中書右丞相、兼太子少傅。
洪武元年二月初四，元濱州守將來到濟南，投降徐達。次日，徐達派遣副將軍常遇春率兵自濟南攻取東昌（今山東聊城市），十二日，東昌被攻克，元守將自殺身亡，其所屬各縣全部投降。至此，山東全境基本平定。
自吳元年十一月至洪武元年三月，徐達所領導的北伐大軍經過約四個月的鏖戰，不僅基本上統一了山東，達到了明太祖朱元璋撤除元朝大都屏障的要求，而且俘虜和收編了大量元朝官兵，繳獲了大量物資。徐達在征戰過程中，不僅能夠充分利用手中的職權，妥善處理有關戰爭善後等問題，而且徐達行軍過程中，軍紀嚴明，對沿途百姓秋毫無犯，並從新收編的元軍將士中挑選精壯者從軍，在補充和擴大北伐隊伍的同時，也解除了後患。徐達的表現，充分展示了他的大將之才，也令坐鎮京師的明太祖大感寬慰，並對其愈加信任。
（三）揮師汴洛
洪武元年三月，徐達統率北伐大軍自山東鄆城出發，經水路逆黃河而上，進取河南汴梁（今河南開封市）。當月二十九日，徐達兵至汴梁陳橋。元汴梁守將李克彝聞訊十分震驚，立即將避難到此，並多次與徐達交鋒的左君弼召來商量對策。李克彝說：“將軍與南朝數次交戰，熟悉他們的陣法。今天我將兵權授予將軍，作為前鋒抵擋徐達，怎麼樣？”左君弼一方麵因為感激明太祖將被俘虜的年邁母親送回，心中早有降意；另一方麵他經過與徐達幾番交鋒後，不僅對徐達心存畏怯，而且在失敗中發現徐達確實精於用兵之道，所以他回答李克彝道：“南朝軍鋒勢不可當，我一看到他們的陣勢就膽怯，所以才投奔到此地。而且南朝徐相國很善於用兵，一直所向無敵，我實不敢受命。”於是，李克彝被迫連夜逃往洛陽，左君弼等率部出城投降，徐達領兵入駐汴梁城。