云县西北黑牛王庄、宁津城歼灭伪军2000余人，打开了抗战的局面。
与此同时，中共中央和八路军总部又决定调115师政治部副主任兼343旅政委萧华率一批干部去黄鲁边区，统一领导那里的武装斗争。随后，萧华率领旅部机关干部100余人由晋西南进抵山东省乐陵县。9月27日，成立了冀鲁边军政委员会，并将该地区部队整编为八路军东进抗日纵队，萧华任纵队司令员兼政治委员，邓克明任参谋长，符竹庭任政治部主任。下辖第5支队、津浦支队和第6支队（由冀鲁边地方武装编成）。第5支队长曾国华，政治委员王叙坤，参谋长刘正，政治部主任刘贤权，下辖第4团（团长褚连三，政治委员朱廷宪）、第5团（团长龙书金，政治委员曾庆洪）、第6团（团长张策平，政治委员赖国清）。第6支队长邢仁甫，政治委员周贯五，副支队长冯鼎平，参谋长程政杰，政治部主任王辉球，下辖第7团（团长李子英，政治委员崔月楠）、第8团（团长杨柳新，政治委员陈德）、第9团（团长杨铮侯）、津浦支队（支队长孙继先，政治委员潘寿才）。
部队整编后，进一步开展游击战争，并成立了几个游击支队。
1938年9月29日，中共中央六届六中全会在延安召开。在这次全会上，毛泽东批评“一切经过统一战线”的口号时说：“在敌后，只有根据国民党已经许可的东西（例如国民党的《抗战建国纲领》），独立自主地去做，无法‘一切经过’。或者估计国民党可能许可的，先斩后奏。例如设置行政专员，派兵去山东之类，先经过则行不通。”
中央军委和八路军总部指示115师所采取的上述行动，就属于“先斩后奏”的性质。
1938年10月，日军占领广州、武汉，抗日战争进入相持阶段。日军加紧对国民党实行政治诱降，而把主要兵力对付共产党的抗日武装。与此相呼应，国民党顽固派也转为消极抗日、积极反共，加紧给共产党和八路军制造麻烦。而山东起义后组织起来的武装既缺经验，又缺干部，派主力部队去山东已是刻不容缓。于是，中共中央决定派115师343旅685团去山东微山湖以西地区，进行抗日斗争。
11月25日，毛泽东、王稼祥、滕代远致电彭德怀，指出“陈、罗率部及陈光旅的主力（两个主力团）全部去山东、淮北为适宜……陈罗东进时，拟分布于新老黄河间广大地区，包括津浦（路）东西、胶济（路）南北在内。尚昆、小平认为可行。”
12月间，朱德，彭德怀向陈光和罗荣桓下达了命令，要求已到达晋东南附近的685团以苏鲁支队名义先行入鲁。先是首战韩庄、崔庄，歼灭伪军王显臣部800余人。不久，苏鲁支队到达湖西与湖西人民武装起义力量组成的山东抗日义勇队第2总队进行合并，并改称苏鲁豫支队（支队的活动范围还包括河南的夏邑县）。当时，彭明治任支队长，吴文玉（吴法宪）任政治委员，支队的任务是巩固和发展湖西抗日根据地。
随后，按照军委部署，115师师部和686团在陈光和罗荣桓的带领下，也于12月20日晚从山西西部的灵石县双池镇出发东进。部队冒着纷纷大雪，越过日军封锁的汾河和同蒲路，翻越了白雪皑皑的绵山，到达了晋东南的八路军总部驻地屯留附近。陈光和罗荣桓与总司令朱德、副总司令彭德怀、八路军副总参谋长左权等在敌后相会，感到分外亲切。朱德还特地到115师驻地看望指战员，给干部们作了形势和任务的报告，还应罗荣桓的请求，为115师的《战士报》题写了报头。罗荣桓等去总部汇报工作时，朱总司令留他们吃饭，并亲自下伙房，给罗荣桓等人炒了一盘辣椒猪肚，大家高高兴兴地吃了一顿饭。
就在这时，国民党为了限制八路军和新四军的发展，决定在敌后成立苏鲁和冀察两个司令部，并无理要求115师归还第2战区建制，并要求八路军在山东的地方部队统一由苏鲁战区总司令于学忠（同时兼任第51军军长）指挥。
如果执行国民党的命令，八路军将很难保持自己作战的灵活性，也不便于发展壮大自己的武装力量。因此，对蒋介石的命令只有置之不理。但是，当时国共正进行合作，为避免国民党找到反共的借口，115师去山东的事最好还要有理由。恰好就在此时彭德怀要去冀南找国民党的冀察战区总司令鹿钟麟，就国民党顽固派袭击八路军一个支队并强令取消抗日政权（冀南行署）的事件进行谈判，115师便以东进支队的名义护送彭德怀。然后，名正言顺地翻过太行山，穿过平汉路，直接进入山东。
就在部队出发前，罗荣桓的爱人林月琴已经临产，罗荣桓前往医院探望。2月14日，林月琴生了一个男孩。即将出发的罗荣桓看到母子平安，放下了心。林月琴一想到自己的丈夫即将出发，心里当然是恋恋不舍，正好孩子的名字还没有取，就让罗荣桓给孩子取个名字。罗荣桓略一考虑，想到115师当时的任务，便说：“部队正在东进，就叫他东进吧！”
说完，便告别了正在坐月子的妻子，踏上了东进的征程。
罗荣桓给儿子起这个名字，切实反映了当时的现实。东面，就是日军的后方。东进，就是到敌人的后方去。后来，罗荣桓给儿子取名字的故事在部队中传得很广，并在以后的作战中，115师的许多部队都用这个名字作为部队的代号。“东进”几乎成了115师胜利的象征。
从晋西到山东有约3000余华里，途中要穿越日军的几道封锁线。在行军过程中，部队遇到了很多困难，因此，有的人就把这次东进称作“小长征”。在这次小的长征途中，115师还配合129师粉碎了日军对山西辽县的进攻。
1939年3月1日，115师东进支队经过河北、河南交界地区，到达了黄河。可是，大家发现河里没有水。原来，由于蒋介石为了阻止日军的进攻，在1938年6月下令炸开了花园口的黄河大堤，致使黄河改道南行，这里的河水便枯竭了。通过这一事实，115师的指战员们了解了蒋介石不考虑老百姓利益的反动本性。
3月2日，八路军115师在代师长陈光和政治委员罗荣桓的率领之下到达鲁西地区，东进成功了。
“罗荣桓陈光领兵马，杨勇将军是先行”
鲁西平原一带虽然有中国共产党郓城中心县委在活动，但还不是共产党领导的较大规模的抗日武装根据地。在当地，日、伪、顽、匪，各霸一方，烧杀抢掠，无恶不作，老百姓处在水深火热之中。八路军115师的到来，给这一带的人民带来了希望。
115师刚到郓城县的张楼宿营不久，八路军到达鲁西的消息就传到了郓城中心县委。县委书记梁仞千立即率领20多人到张楼迎接从平型关下来的老八路（当地群众对八路军主力部队的称呼）。
这些人当中，有驻张楼的国民党郓城县保安司令祝壁臣等当地的开明人士。祝壁臣原为国民党军第88师师长，曾带部队去中央苏区“围剿”过红军，但大敌当前，他已转为拥护八路军的抗日政策。
陈光代师长和罗荣桓政委热情地接待了他们，并与他们进行了交谈。在谈话中，得知在郓城城里的汉j头子叫刘本功，在当地为虎作伥，鱼肉百姓。他的本家刘玉胜带了一个保安团驻扎在郓城西北的樊坝。陈光和罗荣桓决定打下樊坝，消灭刘玉胜的伪保安团，作为对山东父老的见面礼。他们把这个战斗任务交给了686团。
说干就干。3月3日晚上，686团团长兼政委杨勇率领部队冒雨向樊坝开进。全团指战员的棉衣被雨水浸湿了，但个个斗志昂扬。经过激烈的战斗，686团勇猛地冲进了敌人据守的围寨，刘玉胜被生擒。在战斗过程中，郓城守军曾派100余人前来增援，但被115师击退。此次战斗，全歼伪军刘玉胜的保安团共800余人。
这一仗打得干净利落，八路军在鲁西也随之声威大振。
战斗结束后，杨勇赶回张楼，向陈光和罗荣桓汇报作战的具体情况，并请示如何处置刘玉胜。师首长没有急于答复，让杨勇先把刘玉胜带到张楼，待审问后再作处理。
刘玉胜就是郓城人，以前曾在宋哲元的部队中当过排长，在喜峰口参加过对日作战。后来在韩复榘部队中当官的刘本功把他拉回来，让他当连长。山东被日军占领后，刘本功当了汉j保安司令，刘玉胜也跟着当了伪军团长。
审问刘玉胜的工作主要由罗荣桓来做。他与刘玉胜谈了一个多小时，然后与陈光和杨勇商量，看如何处置刘玉胜好。
杨勇说：“在这次战斗中他老丈人肺部中弹，我们的医务人员认真给他治了，刘玉胜很感动，看样子，有些悔罪的表现。”
原来刘玉胜的岳父属于当地的名门望族，有一定的势力。刘玉胜之所以能在郓城县吃得开，在某种程度上赖其岳父的帮助。刘玉胜的岳父不但帮助他，而且社会经验丰富，办事要比刘玉胜老练得多。因此，刘玉胜对他的岳父是十分佩服、尊重，两人之间的感情也非常好。这次686团攻打刘玉胜时，他的岳父被枪声惊醒，慌忙爬起来，蹲在床上，通过窗子向外看，想弄清楚到底发生了什么事情，不想就在这时，一颗子弹打来，正中其腹部。听说岳父负伤了，刘玉胜也顾不上指挥部队，先回来看一下。这时，他的岳父正躺在床上哼哼呀呀地叫着，他的老婆在旁边哭哭啼啼，刘马上吩咐人给包扎伤口。就在这时，686团已攻到窗前，刘玉胜和他的老婆及岳父都成了俘虏。战士们刚刚抓到刘玉胜，杨勇团长就赶到了。他让通信员把医生叫来，给刘玉胜的岳父治伤，很快就包扎好了伤口，并采取措施减轻了老头的疼痛程度，所以当了俘虏的刘玉胜非常感动，当时就说了一些感激的话。
当时，在另外一个村庄里还有枪声，杨勇就问刘玉胜：
“那边小庄里是谁的部队？”
“是我一个营。”刘玉胜回答说。
杨勇说：“那好，你马上写封信，让他们放下武器，立即投降！”
刘玉胜见大势已去，也觉得八路军不错，随即写了一封信，派人送去。
不大一会儿，这个营的官兵就左肩扛着枪，右手举着枪栓，走了过来。对于敌人的投降，八路军是有经验的，他们把准备好的箩筐放在路边，伪军们一个接着一个地把枪栓扔到筐里，然后站队集合。这样，在八路军的强大压力和刘玉胜的配合下，樊坝战斗得以胜利结束。
罗荣桓听完杨勇的话，沉吟了一会说：“我看刘玉胜这样的人是可以争取的，争取过来要比杀掉好。他在当地有一定影响，争取他一个，可以影响一大批人。”
按照罗荣桓的意见，杨勇向刘玉胜申明大义，晓以利害，让他在当地继续组织抗日武装，并派秘书吕鸿到刘玉胜那里去协助他。刘玉胜非常感激，在吕鸿的帮助下，写了一份告当地同胞书：
“玉胜不才，身为中华民国之军人，乃受敌伪之迷诱，沦为卖国求荣之汉j，……樊坝之役，幸被生俘，得蒙不死，倍享优待，并晓以救国救民之大义，教诲良深……玉胜扪心自问，愧悔交集，今获开释，恩同再生。……誓当重整旗鼓，投效抗战，将功折罪，以雪吾耻，以报国人……”
115师在樊坝取得了重大胜利，为老百姓除了一害，一下子在当地树立起了八路军的威信。刘玉胜的告同胞书，在郓城四乡广为张贴，影响也非常大。老百姓为感激八路军，燃放鞭炮，敲锣打鼓，进行慰问。有的人还自动购买棺木隆重安葬烈士，焚香化纸祭奠英灵。这一切曾使115师的干部战士感动得热泪盈眶。
不久，刘玉胜又拉起200多人的队伍，来找杨勇，投奔八路军，参加抗战。
樊坝一仗，打开了鲁西的局面，当地老百姓纷纷要求参加八路军。为了创建鲁西抗日根据地，陈光和罗荣桓决定，从686团中抽出第3营和教导队，再加上师直两个连，由杨勇和何德全、张国华、欧阳文等人领导，留在运河以西地区，称为东进支队第1团（后来改为独立旅）。张仁初、刘西元接任第686团团长和政委，率余下的两个营随师部继续东进。鲁西地区的开辟，使115师在山东又取得了一个立足点。
当时，在老百姓中流传着这样一首歌谣：
正月里来正月正，
东进支队到山东。
罗荣桓陈光领兵马，
杨勇将军是先行。
二月里来杏花红，
奔袭樊坝是杨勇。
活捉伪军五百七，
义释团长刘玉胜。
3月7日，八路军115师686团向东渡过运河，进入泰（山）西地区。师部派出骑兵连，向汶上县城方向侦察敌情。
在这里上演了一场富有传奇色彩的“草桥阅兵”。
战士们穿上日军大衣，骑着缴获的日军大洋马，伪装成日军，来到距汶上城西北五里的伪军据点草桥。伪军的哨兵见有“日本人”来了，慌忙敬礼。化装成日本军官的骑兵教练员，讲了一通谁也听不懂的“日语”，由侦察员扮成的“翻译”把“日本军官”的命令“翻译”给伪军：
“联队长来阅兵，快把队伍集合起来！”
伪军大队长毕恭毕敬地出来迎接。在伪军集合好队伍后，骑兵连指战员突然将其包围，伪军全部缴械。八路军没费一枪一弹，就生俘伪军大队长以下800余人。
3月10日，115师到达东平县东北部的夏谢作短期休整。3月14日，陈光和罗荣桓率115师师部，与中共泰西地委和由泰西人民抗日武装编成的八路军山东纵队第6支队，在东平县常庄会合。随后，驻在鲁西北的区党委也赶到常庄，与115师一起活动。于是，115师在山东又顺利地开辟了泰西这一立足点。
这些事实说明，115师不但顺利地进入了山东，而且还开了一个好头。
中了国民党的圈套
在115师进入山东之前，山东党组织在各地发动武装起义，组建抗日武装，开展游击战争，已经取得了伟大的成就。但是，在党组织内部有一些人认为，国共已经合作了，八路军也编入了国民革命军，八路军就应该更多地听从国民党政府的指挥。尤其是王明，他多次以中央领导人的身份散布“一切经过统一战线”等言论，对八路军中的一些人产生了相当大的影响，特别是对基层组织的影响更大。
当时，石友三的国民党第10集团军，正驻扎在沂蒙山区，但石友三与国民党山东省政府主席沈鸿烈之间有很大矛盾。山东的一些共产党武装就利用他们之间的矛盾，配合石友三抗战。而石友三表面上应付八路军，实际上却与蒋介石联合反共。1939年3月4日，蒋介石致信石友三，信中大意是：华北平原不能让共产党八路军作根据地，贻患未来；石总司令必须与鹿主席协力，将八路军消灭或撵到北边去。
接到蒋介石的信后，石友三立即召开军官秘密会议，制定进攻八路军的作战计划，并将计划付诸实施。3月9日，石友三在蒋介石委任他为冀察战区副总司令兼察哈尔主席之后，根据蒋在信中要他与鹿钟麟共同对付八路军的指示，遂指挥其所属特务旅、第181师、暂编第3师共万余人，同鹿钟麟部相配合，对八路军和抗日根据地发动进攻。其中，石友三把八路军青年纵队的一营人残杀。直到这时，八路军中的很多人才看清石友三的真实面目。
对于沈鸿烈和石友三为代表的顽固派所进行的政治迫害与军事进攻，山东党组织和八路军中的一部分人开始退让过多，反击不力。这主要是因为他们对当时的形势还不能作出正确判断，对国民党中的顽固分子的面目一时还认识