元代海軍的建立經曆了一個漫長的過程。以驍悍精騎著稱於世的蒙古軍進入中原和進兵西域，碰到了江河障礙。為了克服江河障礙，開始建造少量小型船隻（如筏、革舟等）和進行一些小規模的水戰。
蒙古滅金後，蒙古軍與宋軍的作戰日趨頻繁。宋軍依靠水軍，控製江淮防線，抵禦蒙古軍南下。為了適應戰爭形勢的發展，蒙古軍開始著手建立水軍。在此前的太宗四年（1232年），信安（今河北霸州以東）的張進率水軍降，蒙軍才有了水軍。2年後，張進戰死，這支水軍由其子張榮實統領，但實力還不大。蒙古太宗十年（1238年），蒙古軍將領解誠在與宋軍作戰中，奪得宋船千餘艘，以功被授水軍萬戶兼都水監使，建立起第一支較大規模的蒙古水軍。（《元史·解誠傳》）正如近代史學家屠寄所說：“蒙兀（即蒙古）之有水軍自誠始。”（《蒙兀兒史記·解汝輯傳》）
蒙古水軍建立後，在戰鬥中逐漸成長壯大。先後進行巢湖水戰（1238年）、瞿塘水戰（1239年）、夔門水戰（1240年）、淮水水戰（1250年）、馬湖江水戰（1258年）、黑石峽水戰（1259年）等，多數取得勝利，俘獲戰船少則數十艘、多則數百艘。蒙古憲宗八年（1258年），史天澤指揮的嘉陵江水戰，出動戰船千餘艘，三戰三捷，大敗宋將呂文德，繳獲戰船百餘艘。可見當時蒙古水軍已初具規模，戰鬥力已日漸增強。
元代水軍的大發展，是在忽必烈即汗位以後。蒙滅金後，與南宋接壤對峙，雙方的形勢大體與以前金宋對峙時相仿。南宋根據當前形勢，采取了以漢中保巴蜀，以襄樊保武漢，以兩淮衛長江的戰略方針，依靠水軍優勢抵禦元軍的進攻。文天祥於寶佑四年（公元1256年）曾上書進言：蒙軍“未必不朝夕為趨漸之計，然而未能焉，短於舟，疏於水，懼吾有李寶在耳……夫東南之計，莫若舟師，我之勝兀術於金山者以此，我之斃亮於采石者以此。”某種意義上說，金朝之所以未能吞滅南宋，是因為水軍力量薄弱。有鑒於此，忽必烈十分重視水軍的建設，在他即位當年的七月，任命張榮實為水軍萬戶，統領駐河陰、孟州、濱州、棣州、滄州海口等地的水軍1700餘人。（《元史·兵誌一》）加上水軍萬戶解誠所部1760人，（《元史·兵誌·鎮戍》）蒙古水軍已達3400餘人。隨後，忽必烈命部將董文炳造戰船500艘，訓練水兵，又命其他圍困襄陽的部隊利用戰隙教習水戰，擴充水軍。
蒙古至元五年（1268年），蒙軍進圍南宋北部重鎮襄樊，揭開了大規模攻宋戰爭的序幕。在分析戰爭形勢時，忽必烈及其武將文臣都認為，“宋之所恃者江，無江則國亦無矣”，（劉敏中：《平宋錄》）而要突破宋軍江防，非有足夠的水軍力量不可。當時的監察禦史王惲寫了《論大作水軍事狀》，認為“征進舟師固未尚闕，然可大作一軍，召募黃河上下等人，並南人歸順者，兼用其力，舡艦，一依宋法，精選大將，使之專習水戰。”（《秋潤先生大全文集》卷八十六）南宋降將劉整也獻策說：“我精兵突騎，所當者破，惟水戰不如宋耳。奪彼所長，造戰艦，習水軍，則事濟矣。”（《元史·劉整傳》）這些建議，都得到忽必烈的讚同。於是，蒙古水軍的發展速度大大加快。
蒙古至元七年（1270年），劉整等奉命建造戰船5000艘，訓練水軍7萬人。三年後，又在漢水流域的興元（今陝西漢中）、金州（今安康）、洋州（今洋縣）和汴梁造船2000艘，編練水軍5萬餘人。第二年，又在汴梁造戰船800艘。根據史料統計，當時的元水軍，除襄樊前線有劉整和失裏伯所部水軍16萬人左右、戰船萬餘艘外，還有四川也速解兒、按敦、膠州灣蔣德及淄、萊張馬哥等部的水軍。隨著水軍實力的發展，忽必烈調整和加強了前線水軍的指揮機構，把襄樊前線的蒙古4萬戶府辟為水軍鎮撫。