1907年8月8日生于辽宁省金县（今大连市金州区）。早年曾在大连市钱庄当店员，后在奉天省财政厅当雇员。

1925年春考入东北军陆军军士教导队（队长是张学良）学习。

1926年起任副官处少尉副官、沈阳北大营军械官。

1929年考入东北陆军讲武堂第九期。

1930年毕业。东北易帜，张学良就任陆海空军副总司令，随同去南京，任少校团副、少校营长、中校团副。

1935年任东北军3旅7团代团长。不久，被任命为联络参谋。

1936年1月起任东北军第109师第627团中校团长（当时29岁，是东北军最年轻的团长），同年加入抗日同志会，11月参加革命工作，任第627团的抗日青年团荣誉团长，支持和掩护中共党员在该团秘密开展抗日救亡工作。“西安事变”中，万毅率部向渭南前线开进，准备抵御国民党进攻西安的军队。后因发表“张学良把蒋介石扣留，又亲自送回去，他这个事情做得不对，未免太重义气了”的言论，被缪澄流扣押，

1937年2月被反动势力逮捕入狱。

抗日战争爆发后，1937年10月获释后任东北军第57军（军长缪澄流）第112师第672团上校团长，曾参加南京保卫战，全团战没，只身幸免。

1938年1月任东北军第112师第334旅第667团上校团长。

同年3月秘密加入中国共产党，被吸收为中国共产党特别党员。

1940年初任东北军第57军第111师第333旅代旅长。同年9月与师长常恩多（是位具有爱国心和十分同情共产党的领导人）发动针对与日军勾结的57军军长缪澄流的“九？二二”锄奸运动，将反共和勾结日军的军长缪澄流赶出部队。

1941年2月17日被东北军中的反动分子逮捕，关在鲁苏战区监狱。

1942年8月在蒋介石密令处决的前夕，从监禁地逃出，进入滨海抗日民主根据地，找到中共中央山东分局。根据中共中央山东分局指示，旋即被派回东北军，组织领导、改造脱离脱离反动派控制的第111师官兵，与反共顽固派进行斗争，任新111师副师长、师长。

1944年10月20日，奉山东军区命令，新111师改编为八路军滨海支队，任八路军山东军区滨海军区副司令员兼山东军区滨海支队支队长。

1945年6月在中共七大上当选为中共第七届中央候补委员（此时，他参加中国共产党仅仅几年时间）。

同年9月奉命率东北挺进纵队2支队（由胶东军区特务营和滨海、鲁中军区3个连组成，有1200人，万毅任纵队司令员）进军东北。

同年10月至1949年5月任中共中央东北局委员、山东军区东北挺进纵队司令员（至1946年1月）。

1945年11月至1946年1月任中共吉林省工作委员会委员、吉林军区第一副司令员。

1946年1月至7月任中共吉辽省委员会领导成员。1月至8月任东北人民自治军吉辽（辽满）军区副司令员、东北民主联军第7纵队（到1945年底，东北挺进纵队发展到14000人，整编为第7纵队）司令员。

同年2月至5月任中共吉辽省委员会辽北分省委员会委员、吉辽（辽满）军区辽北军区司令员。

同年5月至7月任中共吉辽省委员会辽北省分委员会委员。

同年7月至1947年5月任中共吉林省委常务委员、吉林军区副司令员。

1946年8月至1947年5月任东北民主联军第1纵队（东北民主联军直属第1、第2师和东北联军第7纵队部分部队，在吉林敦化地区合编组成，以第7纵队领导机关为其领导机关）司令员（李作鹏任副司令员兼参谋长，梁兴初任副司令员，周赤萍任副政治委员兼政治部主任。），

1947年5月至12月改任东北民主联军第1纵队政治委员（名将李天佑出任第1纵队司令员）

8月至12月任党委书记。

1946年8月至10月任东北各省（市）行政联合办事处行政委员会委员。

同年10月至1949年8月任东北行政委员会委员。

1948年1月至3月任东北军区暨东北野战军第1纵队政治委员、党委书记。