當朱元璋、馮勝救援安豐時，陳友諒卻率領著六十萬水軍，乘數百艘巨艦，浩浩蕩蕩開向洪都（今江西南昌），朱元璋、馮勝率兵回救，雙方遇於鄱陽湖，在此展開了一場決定勝負的惡戰。陳友諒戰艦高大無比，有“混江龍”、“塞斷江”、“撞倒山”等大戰艦，並且每幾十艘戰艦用鐵索聯結起來，形成旌旗牆櫓，望之如山，其勢甚為嚇人。但馮勝毫不畏懼，在這場戰鬥中，他英勇殺敵，奮不顧身，立下了汗馬功勞，陳友諒中箭而亡。第二年，馮勝又隨從朱元璋攻打武昌，馮勝又一馬當先，衝鋒陷陣，攻克了武昌，幫助朱元璋消滅了實力最強的陳友諒，朱元璋自立為吳王。在接下來的攻克廬州，轉而攻取江西諸路，以及與諸將收取淮東等地的戰役中，馮勝都奮勇衝殺，立下不朽戰功。
消滅了陳友諒，下一個目標就指向張士誠。朱元璋分析了形勢，決定先攻取泰州、徐州等蘇北和淮河下遊地區。馮勝在攻打海安霸、奪取泰州的戰役中，表現出色，取得了成功，他的聲望日盛。至正二十六年（公元1366年）十一月，大軍進攻高郵。朱元璋先是派大將徐達圍攻高郵，久攻未下，於是改用馮勝率軍督戰，派徐達回師解宜興之圍困。馮勝發起猛攻，高郵守將抵擋不住猛烈的攻勢，張士誠的將領俞同僉派遣人前來詐降，相約以推倒女兒牆為內應。
馮勝不知其詐，相信了俞同僉，晚上派康泰率領一百多人躍牆進城，結果被敵人關閉城門全部殺掉。朱元璋知道後大怒，認為馮勝對敵人估計不足，誤中敵人奸計，責打他十杖，並命令他步行到高郵繼續督戰。馮勝又慚愧又悔恨，更加努力地攻打敵人。後來徐達從宜興回師高郵，兩下合兵一處，力量大增，終於攻下高郵，隨後又攻取了淮安。在攻下安豐城中，馮勝擒獲張士誠將呂珍。之後下湖州，克平江，馮勝屢立戰功，使敵人聞風喪膽，望風而逃。論戰功，馮勝僅次於徐達、常遇春，居第三，故晉升為銀青榮祿大夫、都督府右都督，跟隨大將軍徐達北伐，攻下山東諸州郡，蕩平中原，為朱元璋登上皇帝寶座打下了基礎。
開國之功統一大業
至正二十八年（公元1368年）正月，朱元璋登上帝位，做了明朝的開國皇帝。同年，皇太子立，太祖朱元璋任命馮勝兼太子右詹事。
明朝建國之初，雖然中原、江南和閩廣等地已歸屬明朝政府管轄，但周邊地區尚未完全統一。麵對這種割據形勢，繼續完成全國統一事業，是統治者的首要任務。
為平定山西、陝西等地，太祖朱元璋派馮勝率兵渡過黃河，攻汴州、洛陽，下陝州，向潼關開進。潼關守將聞訊，棄關而逃。馮勝遂占領潼關，接著攻取了畢州。在返回汴州時，馮勝謁見巡行至此的太祖朱元璋。太祖對馮勝所取得的戰績甚為讚賞，為表彰他，授予征虜右副將軍，留守汴梁。不久，馮勝又跟從大將軍出征山西，由武陟取懷慶，跨過太行山，攻克碗子城，直取澤州、潞州，在猗氏這個地方擒獲元右丞賈成，在攻克平陽、絳州後又擒元左丞田保保等，並獲將士五百餘人。因馮勝四出征討，屢戰屢勝，太祖朱元璋非常高興，又詔定他為右副將軍，位居常遇春之下。
洪武二年（公元1369年）二月，馮勝又一次率軍渡過黃河，開向陝西。馮勝率師自西安進取鳳翔，李思濟率所部十餘萬人西奔臨洮，馮勝跟蹤追擊，攻取鞏昌（今甘肅隴西），直逼臨洮，降服了李思濟。在回師途中，馮勝跟著大將軍徐達圍攻慶陽。這時，元將擴郭帖木兒遣將攻打原州，以聲援慶陽。馮勝扼住驛馬關口，打敗了擴郭帖木兒的部將，遂攻克慶陽，擒住了守將張良臣。至此山西、陝西才平定下來。
九月，太祖朱元璋召大將軍徐達還朝，留馮勝駐守慶陽，以節製諸軍。不久，馮勝以為關陝既已平定，也引兵回朝。太祖朱元璋為此大怒，說：“你不奉詔令就回來了，我讓你外製敵人，內鎮撫關內，對你寄予厚望，而你卻放棄重任，這是為什麼？”對馮勝大加切責。馮勝也覺得自己把事情鬧大了，忙叩頭請罪。朱元璋念他軍功卓著，功勞甚高，才沒有給他處罰，但賞賜給他的金銀財物，遠不及大將軍徐達的一半。從此以後，馮勝小心為事，唯恐再出錯。
元朝被推翻後，元順帝敗逃到應昌（今內蒙古克什克騰旗西達來諾爾附近）。元順帝和蒙古貴族強烈希望恢複他們統治全國的舊業，不斷地向明朝統治地區發動軍事進攻，導致明朝初年邊疆地區戰事不斷，邊疆人民不得安寧。尤其是尚未撤走的元將擴郭帖木兒在和平一帶為患甚重。為平定邊疆，統一蒙古地區，讓人民過上安穩的生活，朱元璋決定對西北擴郭帖木兒用兵，徹底鏟除他。
洪武三年正月，太祖朱元璋分兩路出兵，命徐達為征虜大將軍，李文忠、鄧愈為左副將軍，馮勝、湯和為右副將軍，向北出征沙漠。馮勝跟從徐達率領的西路軍，一路出潼關、搗定西，打敗了擴郭帖木兒，繳獲數萬匹戰馬。馮勝又分兵從徽州向南出一百八渡，徇洛陽擒元平章蔡琳，進沔州。又派別將從連雲棧攻取興元，移兵吐蕃，征哨極於西北，凱旋而歸。根據馮勝的戰功，朱元璋授予他開國輔運推誠宣力武臣，特進榮祿大夫、右柱國、同參軍國事，封宋國公，年祿三千石。朱元璋還頒給他世券，極盡褒揚。