1894年(光绪二十年)，时年19岁的张作霖离开了高坎镇，不过这个时候他已经成年，而且还有一门可以养家糊口的手艺——相马治马，这个手艺给他带来了好运，此时正值中日甲午战争打响，河北一支清军奉调驻防辽西，他因为给军马治病而与部队熟悉，从而投身军队当了一名骑兵，由于积极追求进步，不久便升任哨长。如果按照这个进程下去，张作霖在腐败的清廷部队里按部就班地干下去，估计到死也不会有多大出息。幸好历史没有给他这样的机会，甲午战败，出关的清军重回河北，张作霖不愿离开家乡，找借口逃回了辽西。
回到老家后，张作霖开了一家兽医店，因为自己的手艺兼且当过兵，为人豪侠大方，一无所有的他居然被赵家庙地主赵占元看中，认为他仪表堂堂，将来定有出息。1895年，张作霖与赵占元的二女儿赵春桂结了婚，这年他21岁，好不容易拥有了一个自己的家。没想到安稳日子没过几天，就又走了霉运。当年跟他有仇的王家听到他回老家，害怕张继续报复，立即向官府汇报，官府派人捉拿张作霖并将其投入了大牢。危难关头，是张作霖的妻子赵春桂央请父亲出钱把张作霖赎回，赎回后的张作霖再也不敢回自己的村庄了，他就住在岳父家。当时正值日俄战争时期，东北已经成为战场，到处都是散兵游勇和乞丐难民。老百姓为了生存被迫组成民团以自卫，大部分村庄还修建了寨墙。赵家庙也成立了一个20多人的民团，但是没有人懂得军事。也是时来运转，张作霖刚好当过一年的兵，而且干的还是一名哨长，有带兵经验，双方一拍即合，经赵占元推荐，张作霖当上了赵家庙民团的头目。张作霖天生就是块带兵的料，在他的调教下，这个20人左右的小小民团很快成为当地战斗力最强的乡勇。他们几次打败了前来骚扰的小股匪帮，名声大振。周边二十多个村子见赵家庙的乡勇如此厉害，也纷纷要求张作霖来管理他们的队伍。这样一来，张作霖的部下达到了一百多人。
在赵家庙的西北，有个大团，团主叫金寿山，手下有100多人。大团的总部设在中安堡，其周围地区是他的保险区。本来，大团的职责是保境安民，可是金寿山的大团却在保险区内横行霸道，无恶不作，比胡匪还凶，老百姓恨极了他们却又没有办法。此时张作霖“仁义”之名已传遍了四乡八里，中安堡的百姓就请张作霖帮忙。张作霖当仁不让，率众赶走了金寿山，还杀了他们几个人，这下张作霖惹祸了。因为金寿山是当地一个著名匪首的部下，这股土匪立即出动几百悍匪偷袭了张作霖的民团。张作霖的民团并非职业军人，平时都在家中种田，只有必要的时候才召集起来。此时遭遇土匪突袭，根本无力抵抗。慌乱之下，张作霖携带妻女率众突围，先是逃到了附近的大村子姜家屯，继而又逃往八角台。在逃亡途中，身怀六甲的夫人赵氏在马车上生下了一个男孩，这就是张学良，当时是1901年6月3日。
据说突围途中，张作霖的把兄弟汤玉麟舍命背着怀有身孕的赵氏一路狂奔(一说是背着张作霖的长女张首芳)，于枪林弹雨中把她救了出来，其情形颇有点三国时期赵云于百万军中单骑救主的味道，所以张作霖取得东北霸主地位以后，对当年跟着他的这帮老兄弟没齿难忘，均委以重任，就是因为他觉得这帮老兄弟虽然才识不高，但忠勇过人，值得信任。后来作为新派代表的郭松龄叛乱，似乎也证明了他对老兄弟异乎寻常信任的正确性，此是后话，在此不提。
突围后去哪里？走投无路的张作霖想到了一个人，这个人就是他当年医马时打过交道的冯德麟(即冯麟阁)，此人现在是辽南巨匪。去冯德麟那里必须经过一个叫八角台的地方。此时的八角台是台安县的一个大集镇，光商号就有50多家，土围子修得比城墙还要高大厚实。镇上也有一个大团，其首领是张景惠。本来张作霖是想从这里借道经过，但是这一借道借着借着就住了下来，倒不是他们不想走，而是人家留着他们不让走了，原因是张作霖名声好，不扰民，而且还带着40多人的队伍，这对于加强八角台的守备力量很有作用。当地商会会长张紫云一再挽留，后来张景惠还主动让贤，甘居副职，把队伍交给张作霖带，张作霖在八角台驻扎了2年，手下队伍发展到200多人，成为他起家的资本。张景惠也因关键时候的主动让贤而颇得张作霖的信任，日后他还担任了张作霖安国军政府的陆军总长等职务。
张作霖的队伍得以发展到200多人，跟他好勇斗狠的土匪个性大有关联。张作霖刚刚在八角台站住脚的时候，手下只有一百人不到，十几条枪，这时来了一个叫做海沙子的土匪，此人势力强大，是辽西巨匪杜立三的手下，有好几百人，几十条枪，双方实力悬殊，开战的话张作霖没有一点胜算。但是张作霖又没有退路，毕竟刚刚代替张景惠接手八角台防务，所有人的眼睛都看着他，张作霖退无可退，只有赌命了。他当着所有土匪的面跟海沙子说：我们双方如果一开打这个村庄就给打乱了，谁也沾不了光，不如这样，就我们两个来对打行不行？你的人在那边，我的人在这边，咱俩同时开枪对打，你把我打死，我这个地方就归你，我把你打死，那你的部下就归我。如果你不敢就算了！
东北土匪斗的就是一个狠字，如果被别人看作胆小，今后就很难在黑道上混了，海沙子被将得没有办法，再说张作霖说得也很在理，只好咬牙和张决斗，两人同时开枪，结果张作霖手臂中弹，而海沙子则被打中头部，当场就死了。这样海沙子的部下都归张作霖了，张作霖的匪帮人数由此扩充到数百人，好几十杆枪了。
杀了海沙子以后，张作霖的名声更响了，既讲仁义，又能斗狠，这在当时的东北就是一张安全的名片。当时辽西有四大土匪，其中一股就是张作霖匪帮，他还有个旗号叫做北霸天。东北土匪都知道有张作霖这样一号人物。