中国人民解放军第41军的前身是东北野战军第4纵队。该纵队是由抗日战争初期中国共产党在胶东地区创建的几支地方武装发展起来的。 1937年12月，中共胶东特委书记理琪等以坚持昆嵛山斗争的红军游击队为骨干，在山东文登县天福山发动抗日武装起义，成立了山东人民抗日救国军第3军。1938年9月，第3军与掖县抗日游击组成第5支队，高锦纯任司令员，宋澄任政治委员，吴克华任副司令员，下辖6个团，共7000余人（12月，归山东纵队建制）。1940年9月，第5支队改称第5旅，吴克华任旅长，高锦纯任政治委员；同时成立新第5支队，下辖第1、第2、第3团。1942年7月，胶东军区成立，新第5支队整编为第16、第17团，与第5旅同归胶东军区领导。1943年3月，胶东军区部队整编，取消第5旅番号，军区直辖第13、第14、第16团；第15、第17团分别编入各军分区。1945年9月，胶东军区部队在对敌大反攻中扩编为山东解放军第5、第6师和警备第3、第4旅。
1945年10月，山东解放军第5、6师共1万余人从海路挺进东北，编为东北人民自治军第2纵队。1946年2月，东北人民自治军第2、第3纵队，合编为东北民主联军第4纵队，吴克华任司令员，彭嘉庆任政治委员，胡奇才任副司令员，欧阳文任副政治委员兼政治部主任，蔡正国任参谋第。下辖由第2纵队第1旅改编的第10旅；由第2纵队第2旅改编的第11旅；由第3纵队改编的第12旅，全纵队共2.3万余人，属辽东（南满）军区领导。1948年1月，东北民主联军第4纵队改称东北人民解放军第4纵队，属东北野战军领导。
1948年11月，根据中央军委关于统一全军编制及部队番号的命令，第4纵队改称中国人民解放军第41军，归东北野战军建制。吴克华任军长，莫文骅任政治委员，胡奇才任副军长，欧阳文任副政治委员兼政治部主任，李福泽任参谋长。所辖第10师改称第121师，蔡正国任师长，李丙令任政治委员；第11师必称第122师，田维扬任师长，吴保山任政治委员；第12师必称第123师，江燮元任师长，张秀川任政治委员。东北人民解放军独立第2师调归该军建制改称步兵第154师，左叶任师长，曹传赞任政治委员。全军共计6.4万余人。和平解放北平后，奉命改编傅作义起义部队的第104军第209师。
1950年1月，第154师调归广西军区建制。2月，该军又改归第四野战军第15兵团建制。1951年1月，进驻潮汕地区执行保卫海防的任务。
中国人民解放军第42军的前身是东北野战军第5纵队。该纵队是在抗日战争胜利后由山海关内几个解放区进军东北的部分部队为骨干发展起来的。 1945年9月至10月，为执行中共中央关于向东北发展的战略部署，陕甘宁边区、晋察冀、华中和山东等解放区抽调部分部队和干部进至东北辽东地区。1946年5月，以辽南军区警卫营、庄河保安团、安东军区保安1团、辽宁军分区警卫1团和延安炮校调进的一部分干部合编组建辽东军区独立第1师；8月，以通化支队、靖宇支队、山东和华中挺进东北部队一部合编组建独立第2师；1947年11月，以安东保安司令部、辽宁军区第3分区基干1团、第4分区独立1团、安东保安第3团合编组建独立第3师。3月31日，在辽阳地区成立东北人民解放军第5纵队，万毅任司令员，刘兴元任政治委员，吴瑞林任副司令员，唐凯任副政治委员。3个独立师依次改称为该纵队下辖之第13、第14、第15师。全纵队3.6万余人。
1948年11月，根据中共中央军事委员会关于统一全军编制及部队番号的命令，第5纵队改称中国人民解放军第42军，万毅任军长，刘兴元任政治委员，吴瑞林任副军长，唐凯任副政治委员，参谋长缺（后廖仲符），郭成柱任政治部主任。所辖第13师改称第124师，徐国夫任代师长，李辉任政治委员；第14师改称第125师，彭龙飞任师长，丁国钰任政治委员，东北军区独立第9师调归该军建制，改称第155师，廖仲符任师长，钟民任政治委员。全军4.7万余人，隶属东北野战军。1950年1月，军部及第125、第126师继续在原地区剿匪；第124、第155师奉命参加鄂西战役，尔后在第二野战军指挥下进入川东作战，完成任务后，第124师归建，第155师拨归中南军区运输司令部建制。2月，该军奉命调驻黑龙江省，隶属东北军区..
1950年10月，第42军首批出国赴朝参战，1952年11月回国。
中国人民解放军第43军的前身是东北野战军第6纵队。该纵队一部的前身为孙中山铁甲车队和北伐战争中的"叶挺独立团"，1927年参加"八一"南昌起义，后由朱德、陈毅率领转战至井冈山，与毛泽东领导的秋收起义部队会师，组成工农革命军第4军（后改称红4军）。1933年6月，编为中国工农红军第1方面军第1军团第2师，下辖第4、第5、第6团。
抗日战争全面爆发后，红2师改编为八路军第115师第343旅第685团，开赴华北抗日前线。1938年底，东进苏鲁豫边区，改称八路军苏鲁豫支队。1940年8月编为八路军第5纵队第1支队，南下华中，增援新四军。11月改为八路军第115师教导第1旅。1941年1月，皖南事变后，改为新四军第3师第7旅，转战于苏北两淮地区。日本投降后，第3师第7旅奉命挺进东北。另一部的前身为"七?七"事变后我党领导的鲁东、冀鲁边的抗日武装，后分别发展为清河军区、冀鲁边军区部队。1944年这两个军区部队合并为渤海军区。抗战胜利后，以该军区主力部队组成6个团先后开赴东北，与冀东一部分武装合编为东北民主联军第7师，辖第19、第20、第21旅。
1946年10月，第3师第7旅与第7师合编为东北民主联军第6纵队，陈光任司令员，杨国夫任副司令员，刘其人任副政治委员，阎捷三任参谋长，徐斌洲任政治部主任。原第3师第7旅改为第16师，原第7师第20旅及第19旅一部编为第17师，原第7师第21旅改为第18师。全纵队2.3万余人。1948年1月，东北民主联军第6纵队改称东北人民解放军第6纵队。
东北解放后，第6纵队在辽宁黑山地区进行整编，1948年11月按照中央军委关于统一全军编制及部队番号的命令，改称中国人民解放军第43军，隶属第四野战军建制。洪学智任军长，赖传珠任政治委员，杨国夫、李作鹏任副军长，刘其人任副政治委员，雷震任参谋长，邓飞任政治部主任。原辖第16师改称为第127师，李作鹏兼师长，张池明任师政治委员；第17师改称第128师，龙书金任师长，徐斌州任政治委员；第18师改称第129师，阎捷三任师长，袁克服任政治委员。原东北军区独立第6师调归该军建制，改称第156师，邓克明任师长，钟人仿任政治委员。全军共6.3万余人。
1952年7月5日，第43军与海南军区合并为海南军区兼第43军。10月，第44军第132师调归第43军建制。1952年11月，第129师师部与海南岛基地共同组建海军西营基地（现湛江基地）。1961年8月撤销第43军番号，部队改属海南军区。