Magallanes había navegado durante mucho tiempo por el Océano Índico por lo que conocía perfectamente las costas asiáticas y africanas, pero no así las americanas. El navegante portugués tuvo la idea de retomar el proyecto de Cristóbal Colón y llegar a las islas de la Especiería navegando hacia el oeste y superando el ya conocido continente americano por su extremo sur y atravesando el Mar del Sur llegar a su objetivo. Este proyecto se lo propuso al rey de Portugal Manuel I pero éste consideró que con la ruta que ya conocían los portugueses bordeando África para llegar hasta los productos asiáticos lo hacía poco interesante, además de los problemas que pudieran surgir por el Tratado de Tordesillas que otorgaba el control de la zona a Castilla. Pero Magallanes no se rindió y tras pedir permiso al rey de Portugal para ofrecer sus servicios en otros lugares, lo que elimina la posibilidad de tratarlo como un traidor, viajó a España y le propuso el mismo proyecto al obispo de Burgos Juan Rodríguez de Fonseca, mano derecha del rey Carlos I y cabeza principal en todo lo referido a las Indias y las expediciones ultramarinas. Esta vez sí que hubo interés.
El 22 de marzo de 1518 se firmó en Valladolid la capitulación de esta gran expedición, por la que se nombraban capitanes generales de la flota a Magallanes y Faleiro, con 50.000 maravedíes de sueldo, que luego fue ampliado a 146.000. Recibían también el cargo de gobernadores y adelantados de las islas que descubrieran; se les otorgaba la veintena de los productos líquidos, la quincena de los de las islas, el quinto de los del primer viaje, así como el derecho a llevar cada año mil ducados en mercancías, y otros gajes considerables concedidos después, además de hacerles caballeros de Santiago. Se les prohibía ir a países pertenecientes a Portugal; y, dada la magnitud de la empresa, la Corona se comprometía a armar cinco navíos, proveerles de todo lo necesario y pagar a las tripulaciones.
El costo de la Armada ascendió a 8.751.125 maravedises, de los cuales el mercader de Haro puso 1.880.000, que tardó 18 años en cobrar; entre otros, también colaboraron con dinero Barbosa, y la Corona (cuatro mil ducados en mercancías, que por falta de fondo costearon los socios).
Mapa de Jorge Reinel de 1519. Puede observarse lo que se conocía de la costa brasileña y la supuesta distancia a la que se encontraban las islas Molucas.
Los preparativos se hicieron en Sevilla, y Magallanes tuvo que ir a Barcelona en 1519, para arreglar complicaciones que habían surgido. Se vio en la necesidad de reclutar a muchos extranjeros, especialmente portugueses, a pesar de que se le había prohibido. El 8 de mayo de 1519, en Barcelona, se extendieron las prolijas instrucciones del rey a Magallanes, inspiradas, en parte, en las que eran usuales en Portugal. Carlos I escribió al rey Manuel, tranquilizándolo respecto a la prohibición de ir a tierras que cayeran dentro de los límites lusitanos. Haro se encargó de la organización de la escuadra.