张作霖决心建立东北海军是有原因的。1922年4月，第一次直奉战争爆发时，吴佩孚乘温树德海军少将的旗舰“海圻”号，巡视秦皇岛、葫芦岛一带，并策应山海关的直系陆军，在葫芦岛发炮一百余发，对奉军造成威胁。5月，奉军失败。在退出山海关时，奉军遭到依附直系的“海筹”、“海容”等军舰从秦皇岛海面大炮的轰击，部队损失较大，甚至白天不敢行动，夜车不敢开灯。张作霖的座车也险被击中。张作霖深感没有海军不能控制海面的痛苦，遂决心建立东北海军。
东北海军的创始人是沈鸿烈。沈鸿烈，字成章，湖北天门人，1882年生。1906年，入日本海军学校学习，加入中国同盟会。1911年毕业回国。武昌起义爆发，沈鸿烈奉命为海军宣慰使，策动长江上下游海军反正。1912年，任南京临时政府海军部军机处参谋。次年，任北京政府参谋本部上校科长，主管海防。1916年，被派赴欧洲观战团海军武官。1918年回国后任陆军大学海军教官。1920年任吉黑江防司令公署中校参谋。1922年，张作霖任命他为镇威上将军公署航警少将处长。
原来，在清朝末年，他在湖北新军充当文书，由两湖总督张之洞派赴日本留学。当时中国海军大权掌握在闽系手中，舰上服役也全是福建人。非闽系的赴日本留学的海军军官就不能在舰上服役，只能在北京海军部候补。以后也只是任参谋等文职人员，没有更好的出路。沈鸿烈不甘寂寞，他谋到吉黑江防司令公署中校参谋的差事，是难得的机遇。
适逢奉军战败退回关外，张作霖自称东三省保安司令，宣布东三省独立，决心加强海防。沈鸿烈便提出了加强海防的具体建议，受到张作霖的赏识，竟被采纳。沈鸿烈把家眷接来东北，在法库买地落户，表示决心跟随张作霖，再加上他的丰富的海军阅历和深湛的海军知识，因而，受到张作霖的信任。张作霖便任命其为东三省保安总司令部八大处之一的航警处少将处长。沈鸿烈原来只是中校参谋，破格提升为少将处长，这在海军军官中还是空前的。后来东三省保安总司令部改为镇威上将军公署。
此后，沈鸿烈便放眼全国，大力招揽人才，把他昔日不得志的同学，尽量吸收到东北来，如凌霄、方念祖、谢刚哲等二十余往日的同学，都是先后投奔他来到东北的。有了这些海军人才，沈鸿烈便沉下心来，创建东北海军。
首先，建立东三省航警学校。该校最初叫葫芦岛航警学校，校址设在奉天省锦西葫芦岛炮台山右侧的八号洋楼。后来改名为东北航警学校、东北海军学校等。当时的校长是海军上校凌霄，教育长是海军中校方念祖，佐理官是海军中校陈华森，学监是海军少校戴修鉴。以下设有兵学教官，分任航海、船艺、枪炮、鱼雷、轮机、气象、海洋，以及海战术，炮战术等科；另有大学数学、物理、化学等专业教官。
学校初设军官班和学兵班两种。学生队有队长、班长，学兵队也有队长。在1921年冬，先招考海军学兵队、水兵队和轮机兵队，各200名。1923年春，在沈阳招考航海将校学生班。报名学历限定中学毕业或有同等学历者。报名者不多，约有五百人，录取40人。又为浙江督军卢永祥代培7名。
这一期入学共为47名。1923年4月1日，正式开学。1926年9月毕业，真正训练出来的在海防舰队服役的只有27名。这是东北海军学校培养的第一期海军军官。第二期招考38名，毕业的只有33名。两期毕业在海防舰队服役的只有60名。
但是，这就逐渐形成了中国海军的东北系，同以正统自居的闽系海军，形成北南对峙的格局。东北海军在中国海军中占有了重要的一席之地。学兵班共办了6期，培养了海军士兵1090名。这所海军学校的创办，为东北海军的建立和发展，做了必要的人才准备。这也是张作霖命令沈鸿烈创办该校的初衷。
其次，筹建东北海军舰队。当时东北自己没有军舰，向外国购买也不容易，只得着手改造商船。向烟台政纪轮船公司购买2500吨级的商船1艘，改造后命名为“镇海”军舰；向日本购买2500吨级的废商船1艘，改造后命名为“威海”军舰。又征召中央海军烟台海军学校的8年制毕业生，来东北海军服役，共招来三十余人。他们都上了军舰，解决了舰队基层军官不足的难题。1923年，“镇海”军舰正式成军，第一任舰长为海军上校凌霄，副长为海军少校盛建勋，轮机长为海军少校张振舣。
第二次直奉战争，奉军获胜。沈鸿烈向张作霖所作的“海防无虞”的保证，得以实现。从此，张作霖对东北海军的建设更加支持。不久，“威海”军舰也继续成军。又将在塘沽接收的1000吨级的俄国破冰船命名为“定海”军舰。还购入了300吨级的日本旧鱼雷艇，命名为“飞鹏”军舰。至此，东北海军舰队就以“镇海”“威海”“定海”“飞鹏”4舰组成。凌霄任代将舰队长。代将是东北海军军衔，介于上校和少将之间。方念祖任“镇海”舰长，宋式善任“威海”舰长，冯涛任“定海”舰长，谢渭清任“飞鹏”舰长。沈鸿烈升任中将司令。第二次直奉战争后，东北海军拥有江防、海防两支舰队，以及一所海军学校。但东北海军的实力还很弱，没有一艘真正的军舰。
再次，巧妙接收渤海舰队。东北海军成立后，面对的劲敌就是渤海舰队。渤海舰队拥有3艘巡洋舰、２艘炮舰、1艘鱼雷艇，是一支实力雄厚的正式舰队。东北海军根本不能望其项背。和平地接收渤海舰队，是沈鸿烈面临的一大难题。但是，直奉二战后，直系失败，归直系管辖的渤海舰队陷入困境。连饷银都发不出来，欠饷达3个月之久。太阿倒持，军令废弛。军官聚赌，士兵放假，军舰失修。舰底的蚌壳附着物厚达一尺多，舰速大大降低。官兵士气消沉，感到前途无望。这给接收渤海舰队提供了难得的机遇。
该舰队中的大型巡洋舰“海圻”号，必须修理，否则就废弃了。当时，北方除旅顺口外，没有可以停放“海圻”军舰的大型船坞。无法，只得于1927年到旅顺口来修理。恰巧同时在该船坞修理的还有东北舰队的“镇海”军舰。两舰隔坞相望，新旧对比鲜明。“镇海”军舰，生机勃勃；“海圻”军舰，死气沉沉。因此，“海圻”军舰的官兵人心思动，都在向往归附东北海军舰队。这里要提一下“镇海”号，“镇海”号可以说是中国海军历史上的第一艘航空母舰。“镇海”舰原是商船，后改为军舰，搭载一种叫做“施来克”的水上飞机。1926年，在所订购的飞机到位后，东北海军成立了“水上飞机队”，把“镇海”号作为水上飞机队的母舰。这样，中国历史上的第一艘航空母舰横空出世。
在这种情况下，他们在军舰修好，刚出旅顺口之际，就通电全国归附东北，全舰官兵欢呼雀跃。在上校舰长袁方乔、协长张衍学和航海大副曹蓝亭的率领下，“海圻”军舰奉命驶向长山列岛，并以此为根据地，长期驻泊。张作霖异常兴奋，下令悉数补发官兵3个月的薪饷，袁方乔升为代将舰队长。要说明的是，该舰绝大部分官兵都是山东人。他们一直受到闽系海军的排挤，同东北海军反而很亲密。这也是他们归附东北海军的心理基础。
“海圻”军舰当时是中国最大的巡洋舰。它是1894年的甲午战争后4年，从英国购买的。辛亥革命前，曾代表中国海军，远渡重洋，赴英国伦敦庆贺英皇加冕典礼。之后，又应华侨的要求访问了美洲，辛亥革命后才回国。“海圻”被称为“海上王”，其航行速度和武器装备，都是世界一流的。因此，“海圻”军舰归附东北，东北海军如虎添翼，壮大了东北海军的实力，鼓舞了东北海军的士气。据说，南京政府的海军部部长陈绍宽曾问到他的部下：“如果东北海军南下，你们作何打算？”部下畏葸地答道：“最好不遇见。”可见，此时的东北海军已经具有很大的威慑力量，驻泊港湾，即可先声夺人。
“海圻”军舰的归附，只是一条军舰的问题，要害是必须尽快接收整个渤海舰队。“海圻”军舰的归附，为接收整个渤海舰队排除了最大的障碍。第二次直奉战争，直军陆战失败了。奉系的势力已经延伸至直、鲁、苏、豫、皖5省。但属于直系的渤海舰队问题还没有解决，这是当务之急。渤海舰队龟缩在青岛海湾，不主动投降。
沈鸿烈采取了强行改编渤海舰队的计策。他策略地拥戴山东督军张宗昌为东北海军总司令，自居海军副司令，下辖两个舰队。第一舰队由原来的东北海防舰队及“海圻”、“江利”两舰组成，舰队长为袁方乔少将，驻泊长山岛；第二舰队由渤海舰队组成，舰队长为凌霄少将，驻泊青岛。依据命令，凌霄只带一两个幕僚就到渤海舰队的“肇和”军舰升起少将旗接任。但夜间凌霄就被该舰军官软禁，限制自由。同时，渤海舰队的“海琛”军舰，也在没有命令的情况下，私自夜间行动，到青岛海湾后海集中，并禁止东北舰队的“镇海”军舰驶离码头。海面戒严，前后海不通，一时形势十分紧张。
沈鸿烈忙中不乱，急中生智，速去济南向张宗昌求救。拥有海军总司令头衔的山东督军张宗昌急赴青岛。在沈鸿烈的策划下，把东北葫芦岛航警学校的海军学生和学兵假扮成陆军，暂充张宗昌的卫队。张宗昌在沈鸿烈的陪同下，率领卫队，登上“肇和”军舰，立即集合官兵讲话。当全舰官兵集合到甲板上时，张宗昌的卫队就迅速地占领了该舰的枪炮位和火药库等要害部位。张宗昌粗中有细，他知道处理突发事件，必须迅速果断，不给对方以任何喘息之机。因此，大字不识几个的张宗昌讲话直截了当。他严厉地问：“我是总司令，你们服从我不？”官兵不知所以地齐声回答：“服从。”张宗昌立刻直接下令：“既然服从，我命令你们马上集合到岸上去听候改编。”就这样，三下五除二，不费一枪一弹，渤海舰队被和平地接收了。
原来的渤海舰队司令温树德被调任军事部海军署长。张宗昌委任部将毕庶澄为舰队司令。后来，毕庶澄转任上海护军使，他打算把舰队带到南方去，不料消息泄露，为免除后患，张宗昌就把他枪毙了。又任命扬州人吴志馨海军少将为舰队司令。1928年，张宗昌以吴志馨与北伐军秘密勾结为由，将吴扣押在济南，4月，张宗昌从济南撤退时，把吴也枪毙了。就这样，沈鸿烈依靠山东督军张宗昌的强大后盾，巧妙地接收了渤海舰队。
最后，东北海军的全盛时期。接收渤海舰队后，东北海军进入了全盛时期。沈鸿烈任海军中将司令，直辖江防舰队。海防拥有两支舰队：第一舰队辖有“海圻”“海琛”“镇海”“威海”“同安”等军舰，以海军少将凌霄为舰队长，驻泊青岛；第二舰队辖有“永翔”“楚豫”“江利”“定海”等军舰，以袁方乔为舰队长，驻泊长山岛。陆上机关有海军学校、陆战队、造船所、海军航空队、海军医院等。这样，东北海军就与福建海军形成了南北对峙的局面。
1927年6月，张作霖命令设立东北海军总司令部，张作霖兼总司令，沈鸿烈任海军上将副总司令，代行总司令职。
东北海军的全盛时期，拥有大小舰只21艘，约有3.22万吨，舰队官兵约3300人。当时全国海军舰只只有4.2万吨，官兵约有5400人。东北海军在全国海军中是占有绝对优势的。东北海军在第二次直奉战争中，起到了牵制敌人的重要作用。
张作霖重视东北海军的建设，不进行直接干预，放手让沈鸿烈去干，收到意想不到的效果。这是张作霖用人策略的一个成功之处。