第二條路子是到海外尋找。說來這也是受了袁珙和黃子澄的啟發。袁珙當年不就曾浮海拜師，從洛伽山上別古崖那兒學會的相人之術嗎？黃子澄不也曾打算“浮海募兵”，來挽救建文朝廷的嗎？沒準兒建文也會帶三二隨從，飄洋過海，到異邦異域暫且住下，以等待複辟的機會呢！
第一條路子好辦。第二條路子就沒那麼簡單。因為他不可能差遣幾位使臣到茫茫大海上飄流。如此，則使臣自己的性命都保不住；就是能保住自己性命，一旦在某座海島上與建文遭遇，他們也沒力量將他抓捕回國的。所以，走第二條路子，必須有一支龐大的船隊。這支船隊既能征服大海的風浪，又能征服建文，以及那些有可能庇護建文的外國人。
於是，“三保太監下西洋”的輝煌壯舉，便因為這種不可告人的目的應運而生了。
大概是永樂二年，或者更早一點兒，永樂皇帝就跟三保兒說：三保兒，你隨朕這麼多年，朕總是“保兒保兒”地喚你乳名兒。今你也大了，再喚乳名兒，不太合適了吧？
三保兒說：皇爺您叫奴才的乳名兒，奴才聽著格外親切，怎不合適呢？合適！奴才即便老了，牙都掉光了，也是皇爺您的“保兒”！
永樂說，不，你都成太監了，再叫“保兒”，那些小黃門、小答應的，聽著也不好聽呢！
三保兒說，沒事兒！“狗兒”他不也是皇爺您叫的嗎？我這“保兒”比“狗兒”還難聽嗎？
永樂笑了。又說，“狗兒”也不叫“狗兒”了。朕已賜他為“彥回”了。
三保兒也笑了。就說，那皇爺您瞧著辦吧。就也給“保兒”賜個名兒吧！
永樂捋須一想，說，你本姓馬，朕賜姓為鄭，就叫鄭和吧。
三保兒趕緊叩頭謝恩。從此便有了“鄭和”。
那時候內官在朝廷已頗受重用。永樂是仇有仇報、恩有恩報的人。凡屬當年跟隨燕王起兵的內官，如狗兒、保兒者，以及在燕師逼近江淮時，那些為燕王通風報信或直接投入帳下的，永樂帝都予以重任。有的出任軍職，如狗兒（即彥回）當了將軍；有的在兵營擔任監軍，如馬靖鎮甘肅、馬騏鎮交趾（這是稍晚些時候的事兒）；有的充當使臣奉敕出國，如李興慰勞暹羅國。而內宮監太監鄭和以及司禮監少監侯顯，也是頗受重用的兩位。
永樂皇帝在給三保太監賜名之後，遂交給他一項重任，即組織船隊，通使“西洋”（即中國南海以西地域），耀武異域。對鄭和他也不必講什麼含蓄，就直截了當地告訴他：出使的真正目的便是查找建文。找到建文，最好是活著帶回國，實在不行，殺死亦可。不過，必須將寶璽帶回。他能否抓到建文，便以有無寶璽為證。
而司禮少監侯顯，永樂帝派他去了西番。估計建文去陸地番國的可能性不大——建文不適應西番的生活——卻也須走一趟看看。侯顯打的“幌子”，則是因了烏思藏（即西藏）僧尚師哈立麻有道術，善幻化，想請他來南京一見。
永樂既將“蹤跡建文”的重點放在了海外，首先要做的，便是打造船舶，打造能抗得住海上風浪的巨船。
“三保太監”從此就忙起來了。
“三保太監”首先在濱臨金川門的三汊河，即燕王設過營帳的龍江附近，擴建了造船廠，謂之“龍江船廠”（後此地稱為“寶船灘”），調集大量工匠建造“寶船”。鄭和親自監工。造船所需的桐油、漆料和棕繩，均由鍾山南麓專設的桐園、漆園和棕園供應。就地又開鑿了若幹大大小小的水塘，作為船塢。建造的船舶，大的長四十四丈，寬十八丈，有十二個大帆，可乘坐一千人。中船長三十七丈，寬十五丈，可乘坐四到五百人。
永樂三年六月十五日，鄭和與副使王景弘，率領將士二萬七千八百餘人，分乘船隻六十餘艘，帶上許多金幣，以及江南的絲織品和江西的瓷器等中國特產，駛出龍江，順江流到了蘇州府太倉縣（今之上海）劉家河人海。沿浙閩海岸線航行到福建五虎門揚帆啟航。
鄭和在海上航行了十數個晝夜，第一站到達的是占城。