Por la Capitulación de Toledo firmada por el rey de Castilla el 26 de julio de 1529 se concedió a Francisco Pizarro 200 leguas hacia el sur contando desde la boca del río Santiago para constituir la gobernación de Nueva Castilla. Desde el paralelo en el que terminaba la jurisdicción dada a Pizarro se le otorgaban a Simón de Alcazaba y Sotomayor otras 200 leguas hacia el sur (llegaba hasta los 21°S), nombrándolo gobernador, capitán general, adelantado y alguacil mayor de la gobernación de Nueva León. Sin embargo Alcazaba y Sotomayor no pudo hacer efectiva la expedición y el rey proyectó (entre 1530 y 1531) entregar los territorios desde Chincha hasta el estrecho de Magallanes a la Familia Fugger de Alemania.
Simón de Alcazaba y Sotomayor fue uno de los adelantados nombrados por el rey Carlos V en las capitulaciones del 21 de mayo de 1534 para explorar y ocupar las tierras americanas. Se le otorgó la Gobernación de Nueva León que iba desde el Atlántico al Pacífico desde el paralelo 36º 57' 09' 'S al 48º 22' 52' 'S. Alcazaba partió del puerto de Sanlúcar de Barrameda el 21 de septiembre de 1534, en una expedición de 250 hombres en dos naves; la que él mismo comanda, "Madre de Dios" y "San Pedro", que llevaba como capitán a Rodrigo Martínez. La Madre de Dios fue separada de la San Pedro por una tormenta a la altura del Río de la Plata y volvieron a encontrarse el 17 de enero de 1535 en el Cabo Vírgenes, hecho que fue relatado por Alonso Vehedor:
Surgimos a la boca del estrecho; al otro día amaneció con nosotros la nao San Pedro, que había estado tomando agua en el puerto de Santo Domingo, y allí descubrió unas islas en la mar de las cuales hallaron mucha cantidad de bestias, aunque en verdad, de la mitad hacia arriba, parecían leones, por el bramido que daban y su ferocidad, y por el cerco que tenían y los colmillos.
Tuvieron la idea de cruzar al Pacífico, pero la situación climática se los impidió, por lo que retornaron hacia el norte bordeando la costa del Atlántico. El 9 de marzo de 1535 Alcazaba fundó en la Caleta Hornos, de la Bahía Gil, 29 kilómetros al sur de la actual localidad de Camarones, en la provincia del Chubut, el "Puerto de los Leones" o Nueva León, que fue el primer intento de fundar una población estable en la Patagonia. Desde allí el mismo día de la fundación, envió una expedición por tierra en busca de riquezas, la cual recorrió la Meseta de Sotomayor internándose unos 70 kilómetros hasta descubrir el actual río Chico, que llamaron "Guadalquivir", en donde tomaron contacto con los tehuelches. Luego de 20 días de marcha, se produce un motín regresando al puerto, en donde fue asesinado Alcazaba y Sotomayor. Rodrigo de Isla logró dominar la sublevación al costo de 80 expedicionarios muertos, algunos de los restantes lograron llegar al Caribe abandonando Puerto de los Leones el 17 de junio de 1535.