ナルバエスはその後、スペイン王カルロス1世によって、フロリダのアデランタード(先遣都督)に任命された。
1527年6月17日、ナルバエスは5隻の船と700名の隊員と共に、アンダルシア州カディス県のサンルーカル・デ・バラメーダから出発した。ナルバエス遠征隊は、1528年4月、嵐と荒波をくぐり抜け、フロリダの海岸に到着した。彼は生き残った300名の隊員と、リオ・デ・ラス・パルマス（現在のフロリダ州のタンパ湾の近くと考えられる）の近くの、敵対的な先住民の中に上陸した。
そこから、強力なアパラチーインディアンの領域に達するまで、ナルバエス遠征隊は内陸のフロリダを通って北方に進んだ。伝説上の黄金も財宝も発見できず、インディアンの敵対心に疲れたナルバエスは、4艘のいかだで内陸から海に戻るように命令した。彼は、船に再び乗ってメキシコへと向かうつもりだったが、船は嵐で破壊された。嵐で4艘のいかだのうち2艘が難破し、ナルバエス遠征隊のほとんどすべてのメンバーが死んだ。嵐で死ななかった80人の男性が、はるか遠くのメキシコシティーに向けて徒歩で進んだ。途中食べ物が不足し、結局4名だけがメキシコシティまで乗り切った。生き残った4名は、アルバル・ヌニェス・カベサ・デ・バカ、アロンソ・デル・カスティーリョ・マルドナード(Alonso del Castillo Maldonado)、アンドレス・ドランテス・デ・カランサ(Andrés Dorantes de Carranza)、そしてエステバニコ（またはエステバン）という名のベルベル人の奴隷のみだった。エステバニコは、今日のアメリカ合衆国である地域に入った、最初のアフリカ人であると言える。
カベサ・デ・バカはNaufragios（難破）という題名の叙述を書き、4名の生存者によるアメリカ南東部から徒歩での旅行について説明した。これは、彼らがスペインの開拓地のあったシナロア州クリアカンに到達するまでに8年の歳月を費やされた長旅であった。
