不甘寂寞，他谋到吉黑江防司令公署中校参谋的差事，是难得的机遇。
适逢奉军战败退回关外，张作霖自称东三省保安司令，宣布东三省独立，决心加强海防。沈鸿烈便提出了加强海防的具体建议，受到张作霖的赏识，竟被采纳。沈鸿烈把家眷接来东北，在法库买地落户，表示决心跟随张作霖。再加上他的丰富的海军阅历和深湛的海军知识，因而，受到张作霖的信任。张作霖便任命其为东三省保安总司令部八大处之一的航警处少将处长。沈鸿烈原来只是中校参谋，破格提升为少将处长，这在海军军官中还是空前的。后来东三省保安总司令部改为镇威上将军公署。
此后，沈鸿烈便放眼全国，大力招揽人才，把他昔日不得志的同学，尽量吸收到东北来。如凌霄、方念祖、谢刚哲等二十余往日的同学，都是先后投奔他来到东北的。有了这些海军人才，沈鸿烈便沉下心来，创建东北海军。
首先，建立东三省航警学校。该校最初叫葫芦岛航警学校，校址设在奉天省锦西葫芦岛炮台山右侧的八号洋楼。后来改名为东北航警学校、东北海军学校等。当时的校长是海军上校凌霄，教育长是海军中校方念祖，佐理官是海军中校陈华森，学监是海军少校戴修鉴。以下设有兵学教官，分任航海、船艺、枪炮、鱼雷、轮机、气象、海洋，以及海战术，炮战术等科；另有大学数学、物理、化学等专业教官。
学校初设军官班和学兵班两种。学生队有队长、班长，学兵队也有队长。在１９２１年冬，先招考海军学兵队、水兵队和轮机兵队，各２００名。１９２３年春，在沈阳招考航海将校学生班。报名学历限定中学毕业或有同等学历者。报名者不多，约有五百人，录取４０人。又为浙江督军卢永祥代培７名。
这一期入学共为４７名。１９２３年４月１日，正式开学。１９２６年９月毕业，真正训练出来的在海防舰队服役的只有２７名。这是东北海军学校培养的第一期海军军官。第二期招考３８名，毕业的只有３３名。两期毕业在海防舰队服役的只有６０名。
但是，这就逐渐形成了中国海军的东北系，同以正统自居的闽系海军，形成北南对峙的格局。东北海军在中国海军中占有了重要的一席之地。学兵班共办了６期，培养了海军士兵１０９０名。这所海军学校的创办，为东北海军的建立和发展，做了必要的人才准备。这也是张作霖命令沈鸿烈创办该校的初衷。
其次，筹建东北海军舰队。当时东北自己没有军舰，向外国购买也不容易，只得着手改造商船。向烟台政纪轮船公司购买２５００吨级的商船１艘，改造后命名为“镇海”军舰；向日本购买２５００吨级的废商船１艘，改造后命名为“威海”军舰。又征召中央海军烟台海军学校的８年制毕业生，来东北海军服役，共招来三十余人。他们都上了军舰，解决了舰队基层军官不足的难题。１９２３年，“镇海”军舰正式成军，第一任舰长为海军上校凌霄，副长为海军少校盛建勋，轮机长为海军少校张振舣。
第二次直奉战争，奉军获胜。沈鸿烈向张作霖所作的“海防无虞”的保证，得以实现。从此，张作霖对东北海军的建设更加支持。不久，“威海”军舰也继续成军。又将在塘沽接收的１０００吨级的俄国破冰船命名为“定海”军舰。还购入了３００吨级的日本旧鱼雷艇，命名为“飞鹏”军舰。至此，东北海军舰队就以“镇海”、“威海”、“定海”、“飞鹏”４舰组成。凌霄任代将舰队长。代将是东北海军军衔，介于上校和少将之间。方念祖任“镇海”舰长，宋式善任“威海”舰长，冯涛任“定海”舰长，谢渭清任“飞鹏”舰长。沈鸿烈升任中将司令。第二次直奉战争后，东北海军拥有江防、海防两支舰队，以及一所海军学校。但东北海军的实力还很弱，没有一艘真正的军舰。
第三，巧妙接收渤海舰队。东北海军成立后，面对的劲敌就是渤海舰队。渤海舰队拥有３艘巡洋舰、２艘炮舰、１艘鱼雷艇，是一支实力雄厚的正式舰队。东北海军根本不能望其项背。和平地接收渤海舰队，是沈鸿烈面临的一大难题。但是，直奉二战后，直系失败，归直系管辖的渤海舰队陷入困境。连饷银都发不出来，欠饷达３个月之久。太阿倒持，军令废弛。军官聚赌，士兵放假，军舰失修。舰底的蚌壳附着物厚达一尺多，舰速大大降低。官兵士气消沉，感到前途无望。这给接收渤海舰队提供了难得的机遇。
该舰队中的大型巡洋舰“海圻”号，必须修理，否则就废弃了。当时，北方除旅顺口外，没有可以停放“海圻”军舰的大型船坞。无法，只得于１９２７年到旅顺口来修理。恰巧同时在该船坞修理的还有东北舰队的“镇海”军舰。两舰隔坞相望，新旧对比鲜明。“镇海”军舰，生机勃勃；“海圻”军舰，死气沉沉。因此，“海圻”军舰的官兵人心思动，都在向往归附东北海军舰队。
在这种情况下，他们在军舰修好，刚出旅顺口之际，就通电全国归附东北，全舰官兵欢呼雀跃。在上校舰长袁方乔、协长张衍学和航海大副曹蓝亭的率领下，“海圻”军舰奉命驶向长山列岛，并以此为根据地，长期驻泊。张作霖异常兴奋，下令悉数补发官兵３个月的薪饷，袁方乔升为代将舰队长。要说明的是，该舰绝大部分官兵都是山东人。他们一直受到闽系海军的排挤，同东北海军反而很亲密。这也是他们归附东北海军的心理基础。
“海圻”军舰当时是中国最大的巡洋舰。它是１８９４年的甲午战争后４年，从英国购买的。辛亥革命前，曾代表中国海军，远渡重洋，赴英国伦敦庆贺英皇加冕典礼。之后，又应华侨的要求访问了美洲，辛亥革命后才回国。“海圻”被称为“海上王”，其航行速度和武器装备，都是世界一流的。因此，“海圻”军舰归附东北，东北海军如虎添翼，壮大了东北海军的实力，鼓舞了东北海军的士气。据说，南京政府的海军部部长陈绍宽曾问到他的部下：“如果东北海军南下，你们作何打算？”部下畏葸地答道：“最好不遇见。”可见，此时的东北海军已经具有很大的威慑力量，驻泊港湾，即可先声夺人。
“海圻”军舰的归附，只是一条军舰的问题，要害是必须尽快接收整个渤海舰队。“海圻”军舰的归附，为接收整个渤海舰队排除了最大的障碍。第二次直奉战争，直军陆战失败了。奉系的势力已经延伸至直、鲁、苏、豫、皖５省。但属于直系的渤海舰队问题还没有解决，这是当务之急。渤海舰队龟缩在青岛海湾，不主动投降。
沈鸿烈采取了强行改编渤海舰队的计策。他策略地拥戴山东督军张宗昌为东北海军总司令，自居海军副司令，下辖两个舰队。第一舰队由原来的东北海防舰队及“海圻”、“江利”两舰组成，舰队长为袁方乔少将，驻泊长山岛；第二舰队由渤海舰队组成，舰队长为凌霄少将，驻泊青岛。依据命令，凌霄只带一两个幕僚就到渤海舰队的“肇和”军舰升起少将旗接任。但夜间凌霄就被该舰军官软禁，限制自由。同时，渤海舰队的“海琛”军舰，也在没有命令的情况下，私自夜间行动，到青岛海湾后海集中，并禁止东北舰队的“镇海”军舰驶离码头。海面戒严，前后海不通，一时形势十分紧张。
沈鸿烈忙中不乱，急中生智，速去济南向张宗昌求救。拥有海军总司令头衔的山东督军张宗昌急赴青岛。在沈鸿烈的策划下，把东北葫芦岛航警学校的海军学生和学兵假扮成陆军，暂充张宗昌的卫队。张宗昌在沈鸿烈的陪同下，率领卫队，登上“肇和”军舰，立即集合官兵讲话。当全舰官兵集合到甲板上时，张宗昌的卫队就迅速地占领了该舰的枪炮位和火药库等要害部位。张宗昌粗中有细，他知道处理突发事件，必须迅速果断，不给对方以任何喘息之机。因此，大字不识几个的张宗昌讲话直截了当。他严厉地问：“我是总司令，你们服从我不？”官兵不知所以地齐声回答：“服从。”张宗昌立刻直接下令：“既然服从，我命令你们马上集合到岸上去听候改编。”就这样，三下五除二，不费一枪一弹，渤海舰队被和平地接收了。
原来的渤海舰队司令温树德被调任军事部海军署长。张宗昌委任部将毕庶澄为舰队司令。后来，毕庶澄转任上海护军使，他打算把舰队带到南方去，不料消息泄露，为免除后患，张宗昌就把他枪毙了。又任命扬州人吴志馨海军少将为舰队司令。１９２８年，张宗昌以吴志馨与北伐军秘密勾结为由，将吴扣押在济南，４月，张宗昌从济南撤退时，把吴也枪毙了。就这样，沈鸿烈依靠山东督军张宗昌的强大后盾，巧妙地接收了渤海舰队。
第四，东北海军的全盛时期。接收渤海舰队后，东北海军进入了全盛时期。沈鸿烈任海军中将司令，直辖江防舰队。海防拥有两支舰队：第一舰队辖有“海圻”、“海琛”、“镇海”、“威海”、“同安”等军舰，以海军少将凌霄为舰队长，驻泊青岛；第二舰队辖有“永翔”、“楚豫”、“江利”、“定海”等军舰，以袁方乔为舰队长，驻泊长山岛。陆上机关有海军学校、陆战队、造船所、海军航空队、海军医院等。这样，东北海军就与福建海军形成了南北对峙的局面①。
１９２７年６月，张作霖命令设立东北海军总司令部，张作霖兼总司令，沈鸿烈任海军上将副总司令，代行总司令职。
东北海军的全盛时期，拥有大小舰只２１艘，约有３．２２万吨，舰队官兵约３３００人。当时全国海军舰只只有４．２万吨，官兵约有５４００人。东北海军在全国海军中是占有绝对优势的。东北海军在第二次直奉战争中，起到了牵制敌人的重要作用。
张作霖重视东北海军的建设，不进行直接干预，放手让沈鸿烈去干，收到意想不到的效果。这是张作霖用人策略的一个成功之处。
筹建大学
原东北大学秘书长、代校长宁恩承写道：“张作霖出身行伍，在绿林生活四年，认识字不多，属于粗人。然而他深知教育的重要。他以为国家的兴衰决定于人民的智力。”①
张作霖曾说道：“凡国家若想富强，哪有不注重教育与实业，会能成功的呢？我们现在这几天正讨论设立东北大学问题。并且，也计划派送留洋的学生。现在救急的法子，就是凡本省自费出洋的，都由省政府酌量予以救济，不使他们失学。”②这段谈话是在１９２１年１２月５日，第一次直奉战争之前。
在东北建立综合性大学，最早提出的是奉天省议会。１９１６年１０月，议员郑英澜提出《整顿学务以储人才建议案》，其中有一条建议，即是“故拟联合吉、黑二省，并设东三省高师及大学”。这是建立东北大学的最初动议。后来，在１９１９年１２月，议员李树滋再次提出创办大学的建议，他提议“每省均设一处大学”。此后，奉天省代省长王永江多次建议张作霖“兴办大学教育，培养专门人才”。教育厅长谢荫昌也积极建议创办东北大学，他认为：“东西洋文明各国，所以号称文明，主要在于学术发达。他们农有农学，工有工学，商有商学。”
对于这些创办东北大学的主张，张作霖欣然采纳。并准备开始启动，就在这时，第一次直奉战争爆发了。东北大学的创办事宜只得暂时搁置。
第一次直奉战争失败后，张作霖在整军经武的同时，便狠抓东北大学的创办。张作霖知道，一个国家的强弱同这个国家大学的多少有直接关系。大学多的国家必然是强国。于是，决心创办东北大学。张作霖命令奉天省长王永江主持其事。１９２２年８月，在省长公署成立大学筹备委员会，聘请教育界名流李树滋、范先炬、佟兆元、林成秀、关海清、谢荫昌、王镜寰、恩格、吴家象、汪兆А⑼踔锉肝薄＃保苍拢踩眨〕す鸱⒉嘉瘟睿钅蠛愠锉咐砉た疲粽篆＇筹备文法科，吴家象筹备干事科。东北大学筹建工作开始走上正轨。
１９２３年１月５日，省长公署批准，以沈阳高等师范学校改建理工科，以公立文学专门学校改建文法科。拟定《东北大学组织大纲》，规定设立６科，即文科，理科，工科，农科，商科，法科。每科又设若干系。后来这些学科发展为学院，即文学院，法学院，理学院，工学院，教育学院，以及后来成立的农学院等。东北大学的经