日军一投降，黄克诚便向中央建议，马上派大部队进军东北，开辟东北战略根据地，被中央采纳。黄克诚率领三师进驻东北。后又向中央提出建立巩固的东北根据地，中央的回电讲：关于建立根据地，你是有经验的。
1945年8月日军投降后，当时国民党军队主力尚在大后方，一时还来不及接管东北。黄克诚在自己的头脑中酝酿出这样一个战略性建议：马上派大部队进军东北，开辟东北战略根据地。他来到新四军军部，建议以华东局的名义请中央迅速出兵东北。但当时任华东局第一书记的饶漱石对黄克诚的建议不予理睬，不同意给中央发电报。黄克诚说不动饶漱石，就返回师部，用师部的电台以他个人名义向中央发去电报，尽管此举有越权之嫌，但他顾不了这么多。
黄克诚在电报中说，尽管蒋介石尚未发动内战，但他对我党提出的和谈毫无诚意，只是把谈判作为欺骗人民、麻痹我军、拖延时间的手段，蒋介石正积极抢占大城市和交通要道，一旦时机成熟，就会发动全面内战。而现在我军主力分散，各根据地之间不能相互策应，很难长期独立支持大规模战争，所以，我党应主动放弃一些地区，集中主力进行决战，创造一片相联系的、条件比较好的战略根据地。
在军事部署上，黄克诚建议尽量多派队伍进军东北，“至少应有五万人，能去十万人最好，并派有威望的军队领导人去主持工作，迅速创造总根据地，支援关内斗争。”而关内则以晋、绥、察三地为第一战略根据地，以山东为第二战略根据地，“其他各地区则成为二大战略根据地之卫星”，以做长期斗争准备。
黄克诚这份电报非常及时，很有见地，内容详尽具体到几乎可以按章操作，受到毛泽东和党中央的高度重视。几天以后，中央就发出指示，确定了“向北发展，向南防御”的战略方针。
1945年9月23日，黄克诚接到上级命令：率领新四军第三师开赴东北。当时关内盛传东北粮食武器多得不得了，去了就能获取。随后，党中央转发了一份先期入东北的同志的报告说：“在沈阳及各地堆积之各种轻重武器及物资甚多，无人看管，随便可以拿到。”9月中旬，苏军电台向中央通报沈阳有日军的大型军火库，存放着10万支枪，可以移交给八路军。
于是，有一种说法盛行起来：到东北的部队根本不用带装备，把手里的武器给当地的地方武装算了，东北的武器足够用的。但黄克诚对此采取了谨慎态度，他不仅要求部队全副武装上路，还给每人发了一件棉衣。9月的苏北，还是阳光灿灿，十分暖和，有人看着太阳就发起了牢骚：“这黄老头子怎么了！专门跟别人唱反调。不但带着装备，还要背着棉衣？”闲言碎语也刮到了黄克诚耳朵里，他一笑置之。
1945年9月28日，黄克诚和洪学智率领自己的部队从苏北淮阴启程，向山东进发，加入了10万大军闯关东开创东北根据地的行列。
黄克诚率部离开苏北的时候，华中局和新四军军部作出指示，部队到达山东后停留一个时期，以巩固部队在山东的力量。黄克诚对此有自己的考虑，从局部看，在山东停留一个时期有利于山东地区的稳固，但从全局看，东北重要得多。蒋介石也会看到东北这着棋。先到东北一天，就主动一天。如果让蒋介石先占有了东北，我军将在战略上陷入极大的被动之中，将会给中国革命造成巨大的损失。想到此，10月4日，黄克诚给中央军委发电，建议部队到山东后不作停留，稍事休整后立即继续大踏步北进。
两天后，中央军委复电：“为迅速达成战略任务，三师部队在到达山东后，应兼程北进，不宜在山东担负战斗任务。”黄克诚的建议被中央采纳了。
10月12日，黄克诚率部到达山东临沂地区，而此时从延安参加完党的七大后的陈毅也到了临沂。陈毅向黄克诚讲了七大的一些情况，黄克诚听了很受启发，遂请求陈毅给正在北进的三师连以上干部训话，陈毅慨然应允。陈毅的讲话，极大地鼓舞了士气，再加之两日的休整，官兵们显得更加精神抖擞。次日，三师全体将士告别陈毅，向着祖国的北方开进。
10月16日，黄克诚、洪学智率部跨过黄河进至渤海区，四天后在东光地区穿过津浦路进入河北境内。然后昼夜兼程，跨永定河，在廊坊地区越过平津路，于11月10日抵达冀东的三河、玉田一带。山海关就在眼前，这时传来一个不祥的消息：国民党军5万余人已抢在三师之前，逼近山海关了。
听到这个消息，黄克诚急忙找来副师长刘震、参谋长洪学智和政治部主任吴法宪等商讨对策，研究之后，一致认为，不能按原计划过山海关，应避免与敌纠缠，绕过山海关，尽快向东北腹地进击。
11月8日，黄克诚电示毛泽东，要求同意三师绕过山海关，向锦州挺进。但，11月12日，东北局又来电让三师先不要向锦州前进，而向义院口、驻操营前进，并授命黄克诚统一指挥新四军三师和梁兴初师，在抚宁地区集结，待机歼灭正向山海关西北的石门寨及抚宁延伸的国民党军队。
东北局的命令与黄克诚的想法发生冲突。11月14日黄克诚发电报给中央军委。电文称：集兵抚宁于我军不利，其理由有三：其一，新四军三师与梁兴初师全部集结于抚宁地区至少还得六天，更何况我部长途行军，极度疲劳，即使是按时赶到，也毫无取胜把握；其二，这一仗打与不打，与进军东北全局关系不大；其三，中央之前已电令我部迅速向锦州集中。
黄克诚电报发出的当天，就收到毛泽东以中央军委名义发来的电报，电报明确指示新四军第三师与山东梁兴初师分路平行前进，限24日前到达锦州地区进行休整。
按照中央军委和毛泽东的命令，黄克诚率部从玉田出发，经冷口出关，于11月25日到达锦西地区的江家屯。至此，新四军第三师，历时两月，跨越苏、鲁、冀、热五省，行程数千里，终于徒步进入了东北，完成了中央既定的战略目标。
黄克诚部在苏北启程时，约有3.5万余人，途中因伤病、牺牲等原因减员3000余人，实际上到达东北的约有3.2万余人。这支部队以后发展成东北野战军中屡建奇功的第三十九军、第四十三军和第四十四军，而黄克诚本人的军事才能在这次进军东北中得到了毛泽东的认同和赏识。
1945年在凛冽的寒风中，林彪对自己的将士讲了这样的话：“今天，我们在东北还没有根据地，还没有家……如果我们没有家，没有房子，就好比流浪者，漂来漂去的二流子，遇到狂风暴雨就会无家可归，无房子可住，就会被狂风吹掉，被暴雨淋死，遇到严寒冬天就会冻死饿死……死无葬身之地。”林彪的话道出了刚进东北时我军的艰难处境和建立根据地的极端重要性。在东北尽快建立根据地的建议最早是由黄克诚提出来的。
1945年的冬天，黄克诚的部队到达江家屯没多久，就得到敌军攻占锦州的消息。东北局急电黄克诚率部切断铁路交通，阻止敌人进入沈阳，黄克诚再次提出了自己不同的看法。
黄克诚在发给中央军委的电报中称：三师出发到东北已1月，仅领到满洲伪币200万元，仅够伙食16天用，一切经费均停发，对人民强迫使用500元、100元之大边币，造成物价飞涨，商店关门，粮食除一部分吃日本存粮外，其余到一处吃一处，吃空烧尽，有如蝗虫，人民怨声载道，这是不得不采取的下策。当时部队到东北后遇到的困难不仅仅是没有粮食吃，其实吃住行都有困难。东北地区尽管军用物资很多，但苏联占领东北后与国民党政府签有条约，不准我军接收苏军缴获的日伪军事物资，战士们没有棉鞋棉帽，棉衣也只有薄薄的一套，而东北的温度已降到零下几十度，可见当时的困难有多大。
11月26日，黄克诚再次给毛泽东发去了一封电报。在电报中他除报告了部队所到达的位置外，着重报告了部队遇到了极为困难的情况，即有名的“七无”说法：“无党(组织)、无群众(支持)、无政权、无粮食、无经费、无医药、无衣服鞋袜等。”黄克诚也谈到了部队士气受到极大影响。黄克诚在上述电报中还指出了另一个重要情况：山海关以西地区土匪极多，他们破坏战场，使部队难以通行。
黄克诚清楚地知道，在东北站稳脚跟比任何其他问题都来得紧迫，同苏北的根据地一样，东北也需要我们自己的根据地。因此，他在电报中写道：“我建议我军暂不作战，进行短期休整，恢复体力，并以一部主力去占领中小城市，建立乡村根据地，作长期斗争之准备。”
黄克诚到东北不久第一个提出了“建立乡村根据地”的问题。历史证明，这一问题的提出和他不久前建议进军东北一样，都是对中国革命的历史进程起了巨大作用。
第三天，黄克诚再次打电报给中央，对于在东北建立根据地的重要性作了进一步阐释。11月29日毛泽东给黄克诚回了电。毛在电报中说道：你可以直接向东北局请示和提出建议。
同一天，中央军委也很快给黄克诚回电了，中央军委的电报中说：关于你部编制、干部配备与活动地区和作战意见等，你均可与林彪坦白商谈，并由你与林向中央提出意见解决。
中央军委的态度与毛泽东的态度是一致的，于是黄克诚立即给林彪发去了一封电报。该电已不再是泛泛地提建立根据地的重要性问题，而是具体写了应该如何和怎样建立根据地的问题了。
林彪很快接见了黄克诚。两人见面后，略作寒暄，黄克诚便直接陈述：我们是疲惫之师，且无根据地作依托，而敌人是乘坐轮船来的精锐之师。策疲乏之兵，挡新羁之马，是不可取的。当前最重要的是建立后方，站稳脚跟，逐渐发展壮大自己，以期将来同国民党军队进行决战。
林彪边听边点头，他采纳了黄克诚的建议，命令新四军三师部队转移到义县、阜新一带，发动群众，进行休整。黄克诚的师部向林彪的司令部靠拢，驻到义县乡下。
黄克诚关于到广大中小城市和农村建立根据地的一系列建议，得到中央和东北局的赞许和采纳。12月22日，中央在致黄克诚的电报中说：“关于建立根据地，你是有经验的。”
12月28日，毛泽东给东北局发来了《建立巩固的东北根据地》的着名电报，明确提出要把东北工作重心放在距离国民党占领中心较远的城市和广大乡村，以便发动群众，建立巩固的根据地，逐步积蓄力量，准备将来反攻。
毛泽东和中共中央要求进入东北的党组织和军队，在东满、西满、北满建立巩固的军事政治的根据地。东北我军便投入到建立和巩固东北根据地的战斗中去了。
进军东北后，黄克诚在鹜欢池初战大捷。东北局西满分局成立后，黄克诚在那里为战士们建一个安定的“家”。在西满，他成功地进行了剿匪作战，使我军站稳脚根。四平街战斗，黄克诚是反对的。
林彪固然知道建立根据地的极端重要性，但怎样才能尽快地把群众发动起来呢？林彪心中没底。黄克诚说，农民没有不热爱土地的，只要我们的政策对路，和过去一样，在东北也同样能把农民发动起来。不久，林彪派了自己的秘书季中全亲自去附近的一个村庄里搞发动群众的试点：土改。
几乎与林彪派秘书去进行“土改”试点的同时，黄克诚已把新四军三师的部队撤向了义县、黑山边境一带，开始了建立根据地的实践：清剿土匪，发动群众，进行土地改革和打击地主的斗争。
此时，国民党军队也并未放松对东北的争夺，他们很快打到了义县，林、黄只得撤到阜新。但是，国民党军又追到阜新，迫于形势，林、黄两人兵分两路，分头发展根据地。
林彪走后，黄克诚将第十旅和独立旅分散在阜新以北、彰武东西地区活动。第八旅和三个特务团拿下通辽，在通辽、开鲁一带做建立根据地的工作。第三师独立旅和活动于彰武地区的独立旅、第十旅在吴信泉指挥下，接连攻占了鹜欢池和泡子车站，随即也在这些地方及其附近地区做发动群众建立根据地的工作。
与此同时，林彪率部取得了秀水河子战斗的胜利，一举歼灭了国民党军的4个营加1个山炮连和1个运输连。秀水河子歼灭战是我军开进东北后打的第一个比较大的胜仗，大大鼓舞了军心士气。
这时候，黄克诚得到消息，东北局已在西满建立了分局和军区。他对未来再一次充满了信心，他准备去西满建立一块牢固的根据地，在那里为共产党的将士们找一个可以避风遮雨的“家”。他随即打电报给东北局，建议把所部的新四军三师部队与西满军区合并，使主力部队与地方相结合，亦使地方有主力部队。不久，东北局任命他为中共西满分局副书记兼西满军区副政治委员。黄克诚走马上任之后，把能抽出来的人几乎都抽出来了。黄克诚后来说：我们要求百分之八十至九十的干部下到农村。
西满根据地是指今日沈阳至长春铁路线以西的广大地区，在这片广阔的地域内，既有一望无垠的草甸子，也有山高林密之地。居住在这一地区内的人口相当复杂，回、汉、满皆有。西满也匪患严重，给黄克诚等西满分局和军区领导人建立根据地带来了极大的困难，建立东北根据地的一个非常艰巨的任务便是“剿匪”，这是与别的地方一个很大的不同方面。
匪患成灾，严重影响了我军在东北立足和根据地的建立、巩固。黄克诚等进入东北的我军领导人痛感不剿灭土匪，这个“家”就不得安生。然而，成了精的东北胡子剿起来却并不容易。
后来有人回忆说：“匪患对我们建设根据地也是一大威胁，那些土匪对地理环境非常熟悉，消息灵通，行动诡秘，出没无常，且全部是马队。我们用大部队进剿，他们就躲到深山老林隐蔽了起来，把他们包围起来，他们就会很快分散突围了出去，比较难对付。”
经过多次实践，黄克诚等人终于摸索出了一套对付土匪的办法，多年后他回忆说：“我们发动指战员出主意想办法，很快摸索出了一套打土匪的经验，打得土匪望风披靡。我组织许多各种规模的骑兵部队，咬住不放，直到歼灭之为止。”
要最终剿灭土匪，当然最主要的还是要依靠人民群众。当地群众深受匪害，早就盼望能剿灭这些胡子，同时老百姓都是当地人，对各路“胡子”的情况熟悉。但要让百姓帮助部队打“胡子”也不是一件容易的事，因为“胡子”心狠手毒，他们知道了是要报复的。百姓有顾虑，尽管他们对各种无恶不作的“胡子”恨得要命，但是他们害怕“强龙压不过地头蛇”，害怕共产党军队红火一时，军队一走，自己便会遭殃，这就要耐心地做工作。工作做到家了，总会有人出来说话的。果然，有人先开了口帮助军队剿匪，后面开口的人就多了。百姓一开口，“胡子”的末日来得更快了。大部分土匪消灭掉后，其残余匪部无处藏身，一直被我骑兵部队追到黑河、漠河一带，被全部剿灭。