1945年春天，萬毅傷愈回到濱海軍區(qū)。7月間，傳來萬毅在中共七大上被選為中央候補(bǔ)委員的消息。其中的一個插曲是，由于電稿翻譯有誤，他的名字在《大眾日報(bào)》上寫成“萬鑷”，引起了大家猜測，更正后，濱海支隊(duì)專門開了慶祝會。不久，傳來日本投降的消息。萬毅指揮濱海支隊(duì)與山東一師相配合，向膠縣日偽軍展開反攻。正在這時(shí)，接到了羅榮桓的急電。

接電后，萬毅和王振乾人不離鞍，馬不停蹄，趕到山東軍區(qū)駐地。一到軍區(qū)，羅榮桓就接見了他們，給他們看了中央的電報(bào)，然后進(jìn)行了談話。

羅榮桓說：“這次你們?nèi)|北，困難很多，頭一條就是要打仗。要給干部戰(zhàn)士講清楚，到東北去，不要留戀大城市，不是去享福。首要的任務(wù)是在那里站住腳，扎下根，要做好艱苦斗爭的思想準(zhǔn)備?！?/p>

羅榮桓沉思了一會兒又說：“你們?yōu)I海支隊(duì)老底子是東北軍，比較熟悉東北的風(fēng)俗民情，到東北扎根比較方便。但是，現(xiàn)在你們部隊(duì)里絕大部分是山東人了，東北人只有百把人了吧？”萬毅、王振乾點(diǎn)點(diǎn)頭。

“你們還可以把原在東北軍一一一師工作過的干部都帶到東北去，發(fā)揮他們的積極作用?！绷_榮桓接著說。

羅榮桓再三叮囑：“到東北后，要依靠群眾，使自己發(fā)展壯大。一定要教育部隊(duì)尊重當(dāng)?shù)厝罕姷娘L(fēng)俗習(xí)慣，密切聯(lián)系群眾，發(fā)揚(yáng)人民子弟兵的光榮傳統(tǒng)。東北人民還沒有見過八路軍，八路軍是什么樣子，主要看你們的了，這是關(guān)系到能不能在東北立足的大問題，你們一定要把部隊(duì)帶好?！?/p>

對萬毅部去東北的問題，羅榮桓考慮得很周到。他告訴萬毅，已經(jīng)請供給部準(zhǔn)備了幾十兩黃金，讓他們帶上以備急需。

萬毅回憶說：“羅榮桓雖然在病中，他還是像送閨女出嫁一樣，對于可能遇到的每一個問題，都替我們設(shè)想到了，語重心長地一一叮囑?！?/p>

告別羅榮桓后，萬毅和王振乾開始準(zhǔn)備開赴東北事宜。當(dāng)時(shí)中央只是命令萬毅部準(zhǔn)備待命出發(fā)，而濱海支隊(duì)在膠縣城下打得正緊，并沒有立即出動。

8月18日，毛主席致電羅榮桓、黎玉：萬毅支隊(duì)即調(diào)東北，經(jīng)河北至熱河邊境待命。該支隊(duì)現(xiàn)有2500人，汰去老弱及開小差者外，能有1500人到達(dá)目的地即好。東北干部凡能調(diào)動者，盡可能調(diào)至萬部。萬電合與軍委聯(lián)絡(luò)。

這時(shí)的安排還只是濱海支隊(duì)。8月20日，毛主席又致電山東分局等：“紅軍占領(lǐng)東北，國民黨力圖爭奪東北。我方除李運(yùn)昌率三個大團(tuán)深入遼寧，冀東冀察兩區(qū)各有一部深入熱河之外，中央決定從山東調(diào)兩個團(tuán)(萬毅支隊(duì)在內(nèi))，冀魯豫調(diào)一個團(tuán)，冀中調(diào)一個團(tuán)，共四個團(tuán)，歸萬毅率領(lǐng)開赴東三省。山東之兩團(tuán)限電到一十天內(nèi)準(zhǔn)備完畢，即行出發(fā)，經(jīng)河北會合冀魯豫及冀中之兩團(tuán)，開至熱河邊境待命。每團(tuán)官兵不得少于一千五百。必須明確宣布去東三省之任務(wù)(乘紅軍占領(lǐng)東北期間和國民黨爭奪東北)。必須配備必要之地方工作干部。三處所集中之東北干部亦望交萬毅帶去。必須有良好之絡(luò)律。……以上告知萬毅，但勿在報(bào)上發(fā)表?！?/p>

這樣，山東出動的部隊(duì)不只是濱海支隊(duì)了。根據(jù)電報(bào)指示，羅榮桓、黎玉等發(fā)出命令：除濱海支隊(duì)全部外，決定：由膠東魯中濱海軍區(qū)特務(wù)營抽出兩個主力連，另一個基干連，不少于450人，加予充實(shí)，配備營級干部，進(jìn)行必要物質(zhì)補(bǔ)充，充分動員，于一周內(nèi)即行出發(fā)，到達(dá)指定地點(diǎn)。膠東抽之營，在適當(dāng)位置集結(jié)，待濱海支隊(duì)路過時(shí)，即列入行軍，魯中抽調(diào)之營，取捷徑直赴渤海區(qū)等候。

此時(shí)，濱海支隊(duì)已會同山東一師攻占了膠縣城。山東軍區(qū)又決定以濱海支隊(duì)為基礎(chǔ)組建東北挺進(jìn)縱隊(duì)，任命萬毅為司令員，周桓為政治委員(未到職，后改任周赤萍)，關(guān)靖寰為參謀長，王振乾為政治部主任。下轄第一、第二兩個支隊(duì)。兩個支隊(duì)連同縱隊(duì)直屬機(jī)關(guān)部隊(duì)共3500余人。

濱海支隊(duì)改編為第一支隊(duì)，共 1800余人，彭景文任支隊(duì)長，李欣任政委。原屬3個團(tuán)，依序改稱為第一二、三大隊(duì)。

第二支隊(duì)由膠東軍區(qū)特務(wù)營和魯中軍區(qū)、濱海軍區(qū)各抽一個營組成，編為第一、二、三大隊(duì)，共1200余人，管松濤任支隊(duì)長，黃明清任政委。

第三支隊(duì)多是山東人，由精干的模范連隊(duì)組成。一大隊(duì)一連曾獲膠東軍區(qū)授予的“攻守兼?zhèn)溥B”的光榮稱號。該連副指導(dǎo)員栗良榮被譽(yù)為“殺敵模范”。電影《共進(jìn)山城》就是以該連三進(jìn)蓬萊城的戰(zhàn)斗故事寫成的。三大隊(duì)七連以紅軍老戰(zhàn)士為骨干，多次擔(dān)當(dāng)尖刀連和突擊隊(duì)，立下了赫赫戰(zhàn)功。不大隊(duì)八連是山東縱隊(duì)八支隊(duì)抽調(diào)骨干組建的，著名戰(zhàn)斗英雄趙永江就是這個連隊(duì)的。二大隊(duì)九連原是山東縱隊(duì)抗日武裝青年隊(duì)，這個連隊(duì)的四班曾榮獲魯中軍區(qū)“爆破英雄班”的光榮稱號。

部隊(duì)組建起來了，如何走呢？按照中央命令應(yīng)走陸路先到冀中，經(jīng)熱河進(jìn)入東北。這條路不僅行程遠(yuǎn)，而且時(shí)間長，而走海路，則既近又快。歸心似箭、急于打回老家去的東北籍干部議論開了，認(rèn)為走海路比陸路好得多。于是，縱隊(duì)便把這一建議向中共山東分局作了匯報(bào)。

山東分局根據(jù)中央指示和各方面情況，決定東北挺進(jìn)縱隊(duì)由膠東渡海進(jìn)入東北。隨后，羅榮桓一面指示膠東準(zhǔn)備船只，一面與萬毅等人詳細(xì)研究部隊(duì)行動中可能遇到的問題，如由哪里上船，需要作些什么準(zhǔn)備，在海上遇見蘇軍巡邏艇怎么辦，遇見美國的艦艇又如何對付，在何處登陸，如何與蘇軍聯(lián)系，等等。

9月2日，由萬毅率領(lǐng)的東北挺進(jìn)縱隊(duì)，分別從膠縣、諸城、博山等地沿著公路向膠東進(jìn)發(fā)，10日至平度地區(qū)集結(jié)整補(bǔ)。膠東軍區(qū)司令員許世友撥給剛在平度戰(zhàn)斗中過來的400名解放戰(zhàn)士，以補(bǔ)充部隊(duì)。

在平度稍作停留后，部隊(duì)繼續(xù)北上，19日到黃縣地區(qū)，23日至25日在蓬萊欒家口集結(jié)。萬毅經(jīng)萊陽赴煙臺。此時(shí)，膠東軍區(qū)在副司令員袁仲賢和行署主任曹漫之的努力下，已收集了漁船三四十只，為部隊(duì)渡海作了各種準(zhǔn)備工作。曹漫之還為萬毅準(zhǔn)備了一套便衣并請了一位俄語翻譯，以便遇到蘇軍時(shí)打交道。

9月23日，萬毅將部隊(duì)交給關(guān)靖寰、王振乾等人，率領(lǐng)一個連的先遣人員，在欒家口碼頭登上一艘機(jī)動油船，先行探察路線，選擇登陸地點(diǎn)。開頭還算順利，漁船劃過藍(lán)色的大海向前行進(jìn)。太陽將要沉落的時(shí)候，刮起了大風(fēng)，浪濤洶涌，船身顛簸。經(jīng)過一天多的煎熬，25日天亮后，遠(yuǎn)遠(yuǎn)地望見菊花島。11時(shí)左右，萬毅一行到達(dá)興城。偵察參謀上岸察看了一番，報(bào)告說，那里除有少數(shù)蘇軍外，就是冀東第十六軍分區(qū)的部隊(duì)了。萬毅令架起電臺，與后續(xù)部隊(duì)溝通聯(lián)絡(luò)。

關(guān)靖寰、王振乾接電后，立即組織部隊(duì)行動。9月底，一支隊(duì)全部安全抵達(dá)興城。其余部隊(duì)，在渡海過程中，有的被大風(fēng)又刮回港口，有的在途中島嶼暫避，有的在海上顛簸了數(shù)日，大部在10月1日下午才到達(dá)興城。第二支隊(duì)第三大隊(duì)乘船漂泊主旅順口的老鐵山登陸，爾后乘運(yùn)煤車趕到沈陽歸建。

9月30日，一支隊(duì)先行乘火車到達(dá)沈陽郊區(qū)。安排好部隊(duì)后，萬毅穿上便衣和警衛(wèi)員一起，坐了一輛小驢拉的膠輪車進(jìn)了沈陽城。小驢車停在了小南門里大帥府。東北局書記彭真和陳云、伍修權(quán)、葉季壯都早已等在里面。他們聽取了萬毅的匯報(bào)，指示萬毅率領(lǐng)部隊(duì)到遼吉兩省交界處清剿土匪，安定社會，建立根據(jù)地。陳云提出，調(diào)出一個連隊(duì)，交給隨同萬毅一同渡海的山東抗大一分校教員孫光，到佳木斯一帶，開展工作。陳云笑著說：“這就算你的第三支隊(duì)吧！”

由于部隊(duì)在渡海前將武器裝備大都留在山東，部隊(duì)急需武裝。經(jīng)與蘇軍交涉，一支隊(duì)在東大營接收了日本軍火倉庫，部隊(duì)全部換上嶄新的三八大蓋，每個班還發(fā)了一挺歪把子機(jī)槍，一個擲彈筒，每個機(jī)槍連裝備了4挺九二式重機(jī)關(guān)槍。戰(zhàn)士們笑得合不攏嘴，笑著打趣：“比起在山東時(shí)可闊氣多了?！?/p>

簡單裝備后，東北挺進(jìn)縱隊(duì)即兵分兩路，向遼吉邊境和長春方向進(jìn)發(fā)了。