Zarpa de Sanlúcar de Barrameda el 25 de septiembre de 1581, en la flota del general Diego Flores, con destino al estrecho de Magallanes. Componían la expedición 23 naves y alrededor de tres mil personas entre soldados, marinos y pobladores para aquellas tierras, Gamboa había sido designado como Gobernador de aquellas tierras.
Cuando la flota estaba lista para zarpar Gamboa comunico al General Flores que no lo hiciera por acercarse un temporal, a lo que Flores se negó a escucharle y la flota zarpó. El temporal azoto la flota durante días sufriendo naufragios de barcos y gran perdida de vidas humanas. En la isla de Cabo Verde durante la estancia de la flota, esta sufrirá la deserción de muchos hombres que no deseaban proseguir el viaje. La flota llega a Rio de Janeiro en marzo de 1582, la gran cantidad de gente que llevan los barcos hacía imposible una vida normal en ellos, lo que produjo; enfermedades y muchas muertes.

Después de muchas dificultades llegarían al Rio de la Plata. El General Valdés recibe de España cuatro naves con refuerzos y vituallas, Valdés abandona la misión y regresa a España quedando al mando de todo Sarmiento de Gamboa, desde este momento Gamboa organiza la flota y tras varios meses, abandona el Rio de la Plata con cinco buques y unos 600 hombres. Llega al estrecho de Magallanes el 1 de febrero de 1584, la expedición había tardado dos años y medio en llegar, pero Gamboa no desistía de su intento de colonizar el estrecho, tomaría posesión de aquellas tierras, fundando el 11 de febrero de 1584 la ciudad Nombre de Jesús, levantando las primeras viviendas y la Iglesia de Nuestra Señora de la Purificación. Al poco tiempo uno de los capitanes llamado Diego de Ribera, se amotina y con tres naves de las cuatro que tiene Gamboa se marchan a España los amotinados. Con los que le quedan, unas trescientas personas, mal vestidos y con pocas provisiones. Gamboa comprende que la naturaleza del lugar no puede mantener tanta gente, teniendo que trasladarles a otro lugar. Ordena que un gran grupo de hombres se traslade al nuevo asentamiento, al llegar, funda la ciudad Rey Felipe, Gamboa comienza en este lugar una nueva construcción, pero volverá a fracasar.

El 22 de junio de 1586 emprendió el regreso a España en la nave que le queda, a pedir refuerzos y vituallas para la gente que dejaba allí, en la travesía fue atacada por buques ingleses, hecho prisionero y conducido a Inglaterra, después de ser interrogado quedo en libertad. En octubre de 1586 Gamboa mientras cruza Francia es capturado por los Hugonotes quienes piden un elevado rescate. Felipe II se niega a pagar, pero pasado un tiempo el Rey paga el rescate, era el año de 1589, después de ocho años de aventuras Gamboa volvía a España. A su llegada Gamboa pidió los socorros para la gente del Estrecho, pero el Rey no le haría caso. Sería nombrado almirante de la Armada que protegía a las naves de las Flotas de Indias. Moriría mientras dirigía una flota cerca de Lisboa el 17 de julio de 1592.