既然号称福建海军，当然，在旧中国武人们的心里，海军将领必须是福建人。所以当时中国海军大权全部掌握在闽系手中，舰上服役的包括打杂的也全是福建人。如果你的户口不是福建的，对不起，就算你有通天的本事，最好的去处就是在北京海军部当候补。候补得再好，老天眷顾让你升官，充其量也就是个文职的参谋人员，没有更好的出路。沈鸿烈是个不甘寂寞的人，他想方设法跑到东北，得到了吉黑江防司令公署中校参谋的职位，这在当时的海归一派中已经是属于极高的待遇了。
恰在此时，奉军战败退回关外，张作霖自称东三省保安司令，宣布东三省独立。颇有眼光的沈鸿烈多次通过不同渠道，向张作霖提出加强海防的具体建议，再加上他丰富的海军阅历和深湛的海军知识，张作霖比较信任他。同时张作霖正在为建设东北自己的海军而犯愁，两下是一拍即合。
1922年，张作霖任命沈鸿烈为镇威上将军公署航警处少将处长，这个航警处可是东北军事的核心部门，东北总共有八大处，航警处就是其中之一。沈鸿烈原来只是中校参谋，破格提升为少将处长，这在海军军官中可谓空前。
获得任命后，沈鸿烈的积极性陡然高涨，他大力招揽人才，极力扩充海军实力。想到过去自己的遭遇，他对旧军队排挤异己的行为十分不满，想到有学问的人总是得不到重视，他也是特别痛恨。在他终于有了真正的兵权后，他开始大力革新，重用学术人才。当年跟他一起留学的同学们多数是不得志的，于是他东奔西走，使劲张罗，将那帮同学一个不落的全都招到东北来。凌霄、方念祖、谢刚哲等人就是在那个时候投奔东北海军的，后来这几个人也为东北海军的建设立下了汗马功劳。
有了张作霖经济上和行政上的支持，再有了可用的人才，沈鸿烈终于甩开膀子，开始了创建新式海军的计划。
决定战争胜负的关键因素是人，而不是武器，尤其是技术含量很高的海军更是如此，这点他是心知肚明的，于是培养海军人才就成了当务之急。这第一步，就是建立东三省航警学校。
航警学校最初叫葫芦岛航警学校，后来改名为东北航警学校、东北海军学校等，校长就是被他招募来的同学、被张作霖授予上校军衔的凌霄，教育长是海军中校方念祖。学校的专业设置门类齐全，航海、船艺、枪炮、鱼雷、轮机、气象、海洋、海战术、炮战术等学科应有尽有。不光如此，为了培养面向20世纪的复合型人才，学校还开设了数学、物理、化学等常规大学才有的专业。
学校有两个班级差别，分别叫学生班和军官班。顾名思义，学生班就是培养军舰上的专门人才的，比如轮机手、鱼雷手、操炮手等，而军官班就是培养舰艇中高级指挥官的。
军官班第一期入学的学生一共47名，1923年4月1日正式开学，1926年9月毕业，学制三年。最后真正拿到毕业证在海防舰队服役的只有27人，这是东北海军学校培养的第l期海军军官。其他的人不是中途退学(家境不好或生病等)，就是考核不合格被勒令退学的，可见沈鸿烈办学的宗旨是宁缺毋滥，还是很严格的。第2期招考了38人，最终顺利毕业的也只有33名，有5个人考试老是不及格(还作弊)，不得不让他们回家种地去了。
学兵班一共举办了六期，培养了海军士兵1090名。
总之，通过航警学校的培养，东北海军开始从有名无实到人才济济，形成了一整套海军培养、指挥、作战的系统，为东北海军自成一家打下了坚实的基础，这也是张作霖最希望看到的结果。
有了人才，没有武器也不行，用嘴皮子喊是喊不倒敌人的，海军的武器就是舰艇，所以这第二步，当然就是筹建东北海军舰队。
当时东北自己没有军舰，张作霖打算向外国买，但这很麻烦。一是海军强国比如英国、法国等不愿意卖给他，因为他们支持的是吴佩孚的直系，根本不愿意看到受日本支持的张作霖做大，所以办起事情来并不痛快。别以为有钱好办事，到关键时候有钱也没用。现在看出来张作霖为什么大力发展兵工厂了吧，就因为他知道吃人的嘴短、拿人的手软。另外一个原因就是购买军舰不像购买枪支弹药或其他物品那么容易，一艘军舰从设计到制造是很费时日的，今天签合同，等拿到军舰怕是要等两三年之后了。
购买太麻烦，张作霖便指示沈鸿烈打起了改造商船的主意。他向烟台政纪轮船公司购买了一艘2500吨级的商船，经过一番改造后命名为“镇海”军舰，第一任舰长为海军上校凌霄，副舰长为海军少校盛建勋，轮机长为海军少校张振舣。
后来张作霖又向日本购买了一艘2500吨级的废商船，改造后命名为“威海”军舰。又征召中央海军烟台海军学校的八年制毕业生，来东北海军服役，解决了舰队基层军官不足的难题。
接着又将在塘沽接收的1000吨级的俄国破冰船命名为“定海”军舰，还购买了一艘300吨级的日本旧鱼雷艇，命名为“飞鹏”军舰。
至此，东北海军舰队就以“镇海”、“威海”、“定海”、“飞鹏”四舰组成。凌霄任代将舰队长(代将是东北海军特有的一个军衔，介于上校和少将之间，相当于某些国家军衔中的准将)。方念祖任“镇海”舰长，宋式善任“威海”舰长，冯涛任“定海”舰长，谢渭清任“飞鹏”舰长，沈鸿烈升任中将司令。
不过此时的东北海军的实力还很弱，实际上没有一艘真正的军舰。因为能叫出名字来的那几艘船，都是人家用烂了的，真打起仗来管不了大用处。
张作霖不是不知道海军的实底，他也在费尽心机想办法，为海军搞来急需的军舰。在这件事上，张作霖玩了一招极其高明的拿来主义，那就是整体接收了渤海舰队。
东北海军成立后，面对的最大敌人就是渤海舰队。渤海舰队拥有三艘巡洋舰、两艘炮舰、一艘鱼雷艇，是一支实力雄厚的正式舰队，东北海军根本不是人家的对手。一旦真打起来，东北海军在渤海海军面前可能连一发炮弹都发射不出去，就被人家缴械了。既然不是人家的对手，短期内凭自己的实力购买也不可能，那怎么办?难道等人家打上门来再后悔?张作霖决定干脆一不做二不休，直接将渤海舰队拿来给自己。
他这么想不是没有道理的。因为中间发生了第二次直奉战争，直系失败了，归直系管辖的渤海舰队陷入困境，连顶头上司都跑了，工资都不知道找谁要去，他们当兵吃粮的能怎么办?于是军官聚赌、士兵放假、军舰失修，官兵士气消沉，感到前途无望。
渤海舰队中有一艘有名的大型巡洋舰，名叫“海圻”号。这艘“海圻”号可是大有来头，它是当时中国最大的巡洋舰，是1894年的甲午战争后四年，从英国购买的。辛亥革命前，曾代表中国海军远渡重洋，赴英国伦敦庆贺英皇加冕典礼。之后，又应华侨的要求访问了美洲，辛亥革命后才回国。“海圻”被称为“海上王”，其航行速度和武器装备都堪称世界一流。
但是多年来直系军队拖欠军费严重， “海圻”军舰早已年久失修，再不立刻修理就只能废弃了。1927年， “海圻”军舰到旅顺口来修理，闻听此消息，张作霖马上命令将自己海军中最好的军舰“镇海”号做了一番布置，也开到旅顺口来“修理” 。于是分属不同舰队的两艘军舰被人为地摆在了一起，两舰隔坞相望，新旧对比鲜明。“镇海”军舰生机勃勃； “海圻”军舰死气沉沉。“海圻”军舰的官兵看着衣着光鲜的东北海军将领，再看看自己那一身早已过时的旧军舰和破烂军服，不由得大发感慨，产生了投奔东北的想法。
而张作霖也暗中安排人去“海圻”号上嘘寒问暖，表示张作霖对他们很是关心和看重。其实该舰绝大部分官兵都是山东人，他们一直受到闽系海军的排挤，在心理上反而与东北海军更亲近。“海圻”上的官兵们一致决定改换门庭，于是他们在军舰修好、刚出旅顺口之际，就通电全国归附东北。在舰长袁方乔的率领下，“海圻”军舰奉命驶向长山列岛，并以此为根据地，长期驻泊。
张作霖当即下令足额补发官兵已经被拖欠了三个月的工资，将袁方乔升为代将舰队长。此时的张作霖兴奋异常，有了“海圻”军舰的加盟，东北海军终于可以算得上一支真正的海军了。
有了初一，就有十五。“海圻”毕竟只是一艘军舰，整个渤海舰队还没有被张作霖掌握。第二次直奉战争后，奉系的势力已经延伸至直、鲁、苏、豫、皖五省，但渤海舰队因为在海上，奈何他们不得，他们也龟缩在青岛海湾，就是不主动投降。
沈鸿烈有点着急了，采取了强行改编渤海舰队的计策。他拥戴山东督军张宗昌为东北海军总司令，自居海军副司令，将“海圻”、“江利”两舰组成海军第一舰队，而将原来的渤海舰队改为第二舰队，任命凌霄担任舰长。凌霄只带了一两个人就动身去接收“肇和”军舰，没想到当天晚上他就被军舰上的军官软禁。同时，渤海舰队的“海琛”军舰也在没有命令的情况下，私自夜间行动，到青岛海湾后海集中，并禁止东北舰队的“镇海”军舰驶离码头。一时间海上全面戒严，形势十分紧张。
沈鸿烈遇到这一变故，一下子有点慌神。不过毕竟是日本军校培养出来的学生，又多次出国学习，多年锻炼的军事素质发挥了关键作用。他知道现在只有一个人能处理这个问题，于是他火速前往济南调张宗昌来灭火。
在沈鸿烈的策划下，海军总司令张宗昌急赴青岛，并把东北航警学校的海军学生假扮成陆军，暂充张宗昌的卫队。张宗昌在沈鸿烈的陪同下，率领卫队，登上“肇和”军舰，立即集合官兵讲话。当全舰官兵集合到甲板上时，张宗昌的卫队就迅速地占领了该舰的枪炮位和火药库等要害部位。
张宗昌号称“狗肉将军”，本身是个大老粗，做起事来也是作风粗野，不过此时他倒真是最适合处理这个问题的人。他没有讲究什么策略，也不会做政治思想工作，更不会与人拉家常攀亲戚，一上来就直奔主题： “我是总司令，你们服从我不?”
官兵们是丈二和尚摸不着头脑，弄不清他葫芦里卖的什么药，只是茫然地喊口号：“服从!”
“那好，你们马上集合到岸上去听候改编。”
“是!”
如此复杂的局面，他张宗昌居然就用这么简单的方法解决了，不得不说一句： “人才不一定要最好的，而是要最合适的!”渤海舰队就在他两句连文理都不通的喊话中被和平接收了。
接收渤海舰队后，东北海军拥有了两支舰队：第一舰队辖有“海圻”、“海琛”、“镇海”、“威海”、“同安”等军舰，以海军少将凌霄为舰队长，驻泊青岛；第二舰队辖有“永翔”、“楚豫”、“江利”、“定海”等军舰，以海军少将袁方乔为舰队长，驻泊长山岛。
整个东北海军拥有大小舰只2l艘，共约有3．22万吨，舰队官兵约3300人。当时全国海军舰只只有4．2万吨，官兵约有5400人。东北海军在全国海军中占有绝对优势。这样，东北海军就与福建海军形成了南北对峙的局面，东北海军进入了全盛时期。