记载：
北逐元人之扰边者，至鸦寒山还，调燕山左护卫。从燕王出塞，至黑松林。
此战之后，张玉因功被调任燕山左后卫，从此，归于燕王朱棣麾下。张玉在朱棣麾下很快展现了自己和其他将领的不同。经过黑松林之战和征讨野人诸部，张玉的能力得到了朱棣的认可。史载：
以骁果善谋画为王所亲任。
张玉最大的特点是善于出谋划策，和他并列的另一位战将朱能则更擅长拼杀，《明史·朱能传》中如此概括他们二人：
（朱能）能于诸将中年最少，善战，张玉善谋，帝倚为左右手。
这句话的意思是：朱能在燕王的亲信中年龄最小，却最骁勇，他和张玉二人，一个善战，一个善谋，是朱棣最倚重的两位将领。
在朱元章的众皇子中，燕王朱棣的能力较为突出。而且，早年间朱棣曾跟随徐达出塞，对治军方面颇有心得。朱棣最擅长的就是和军中将领打成一片，视将士们如手足，这就是他麾下将士们愿意追随他的重要原因。
张玉从洪武二十四年调任燕山左后卫，到靖难之役之前，他在朱棣麾下一共待了7年时间，远不如他在北元的时间长。朱棣当年为了让张玉死心塌地地跟着自己，不仅待张玉如兄弟，还仅纳了张玉的女儿为侧妃。朱棣的王妃徐氏（徐达之女）经常派人给张玉的妻子和儿子送去关怀。这样的待遇，是张玉在北元所不曾有过的，张玉焉能不被朱棣折服？
明仁宗朱高炽登基后，曾回忆朱棣评价张玉的一段话：
张玉识见谋略，卓然老成，非诸侯所及，且端方有匡直之益，诚难得也。
可见，在朱棣的心目中，张玉“非诸侯所及”，且为人端方，是非常难得的将才。
良匠无弃材，明君无弃士。
朱棣能在众多将校中看出张玉之才，并用心思去拉拢他为己所用，这也是他能够成功的因素之一。
二、藩王起兵众将戮力，张玉骁勇连败两将
明朝洪武三十一年五月，朱元章驾崩，皇太孙朱允炆继位，是为建文帝。朱允炆登基后，身后以齐泰、黄子澄为首的亲信极力怂恿朝廷削藩，而年轻气盛的朱允炆也不愿看到藩王势大，所以，在朱元章尸骨未寒的情况下，朱允炆派李景隆突袭了周王朱橚的府邸，将朱橚及其儿子贬为庶人。
《明史·本纪第五》记载：
惮燕王强，未发，乃先废周王橚，欲以牵引燕。
意思是，建文帝从一开始就忌惮燕王，之所以先削周王，就是因为周王朱橚是燕王的同母弟，想借此来剪掉燕王的羽翼。
所以，周王被削之后，燕王麾下的将士有些义愤填膺，有急性子的甚至怂恿燕王起兵自立。而此时的张玉并没有发表看法，因为不管朱棣做出什么样的决定，他都会义无反顾地支持。
接下来的一年，朱允炆又削掉4位藩王，其中朱元章的第十二子、湘王朱柏因为不堪折辱，直接举火自杀了，这些消息深深地刺激到了朱棣。这时，朱棣身边的谋士姚广孝也劝朱棣“只信天道，不论民心”，朱棣终于下决心暗中囤积粮草、打造兵器，准备起兵。
建文元年七月，建文帝给北平布政使张昺、指挥使谢贵、张信三人送来密旨，要求他们暗中设计擒获朱棣。张昺、谢贵二人领命，张信表面上遵旨，私下里却向朱棣通风报信。朱棣大惊，连忙和姚广孝商议对策。结果，朱棣让张玉、朱能率军埋伏在王府内，然后邀请张昺、谢贵二人上门，就这样，张昺、谢贵二人在猝不及防的情况下被张玉和朱能杀掉。接下来，朱棣以“清君侧”为名，发动靖难之役。
燕王朱棣虽然身在北平，但他仅仅在藩邸，燕王府之外的地方名义上还归朝廷节制。所以，接下来就是张玉大显身手的时候了。《明史》记载：
建文元年，成祖起兵。玉帅众夺北平九门，抚谕城内外，三日而定。