海軍131艦隊成立於民國34年4月，番號為海防第二艦隊，民國38年5月1日更名為海軍第二巡防艦隊。民國55年4月1日改編為海軍巡防第一艦隊，「司令」改稱為「艦隊長」，民國63年10月1日整編為「海軍巡防艦隊」民國65年1月1日更名為「海軍131艦隊」。

民國77年7月1日海上巡邏大隊暨1至4中隊（原軍情局海上工作大隊暨1至4中隊）改隸海軍併屬本隊，更名為「海軍海上巡邏大隊」暨「海軍海上巡邏第1至4中隊」。

遵國防部81年12月16日(81)迪逢自第2278號令，自民國82年1月1日起裁編海上巡邏大隊，並增列海軍272戰隊隸屬本隊。

民國86年9月1日奉總部(86)梃裝字第733號令辦理主戰兵力調整移編，於民國86年10月1日生效；兵力分配計：212戰隊下轄惠陽、安陽、遼陽、瀋陽、正陽，252戰隊下轄建陽、漢陽、德陽、雲陽、邵陽等十艘。因應新一代兵力整建，本隊所屬PF(玉山艦、華山艦、文山艦、福山艦、廬山艦、壽山艦、鍾山艦)DE(太原艦) 、LPR(天山艦、泰山艦)PCE(武勝、居庸、平靖)等艦相繼於民國87年3月前依令除役；民國88年2月2日遵總部(88)揖裝字第231號令：惠陽、安陽、漢陽等三艘移編海軍168、146艦隊，於民國88年3月16日生效。

民國88年8月30日奉總部(88)悍戰字第1959號令成立「假想敵艦隊」，致力於共軍戰術戰法研析，研擬剋制對策，俾達成知敵勝敵之目的。

民國88年9月20日奉總部悍戰字第2131號令海軍272戰隊暨PCL-1至9艇自民國88年121日起移編至海軍124艦隊，令奉國防部(89)奧奉字第0342號令核定、總部(89)揖裝字第0231號令頒錦江級艦等後續艦成軍隸屬本隊；下轄212戰隊計：龍江艦、淡江艦、鳳江艦、高江艦、湘江艦、昌江艦、珠江艦，另252戰隊計：綏江艦、錦江艦、新江艦、曾江艦、金江艦、資江艦、鄱江艦等共計14艘。

另因應「精進案」之推動，本隊奉總部(92)泰編字第1109號令92年12月16日汰除雲陽及正陽軍艦，復於93年6月1日奉總部泰編字第0930000330號令汰除遼陽及邵陽軍艦，同年12月1日奉總部泰編字第0930001020號令汰除建陽軍艦。

民國94年1月13日治戰字第0940000434號令示本隊德陽軍艦於94年4月1日汰除；民國94年9月15日總部泰研字第0940000902號令示本隊瀋陽軍艦於95年1月1日生效汰除，至此本軍陽字型艦已全數汰除。