Em março de 1505, aos 25 anos, Magalhães alistou-se na frota de 22 navios enviados para acolher Francisco de Almeida como primeiro vice-rei da Índia portuguesa . Embora o seu nome não apareça nas crónicas, sabe-se que aí permaneceu oito anos, em Goa, Cochim e Quilon. Participou de diversas batalhas, incluindo a batalha de Cananor em 1506, onde foi ferido. Em 1509 lutou na batalha de Diu.

Depois de ver as suas propostas de expedições às Ilhas das Especiarias repetidamente rejeitadas pelo rei Manuel de Portugal, Magalhães recorreu a Carlos I, o jovem rei de Espanha (e futuro Sacro Imperador Romano). Sob o Tratado de Tordesilhas de 1494, Portugal controlava as rotas orientais para a Ásia que contornavam a África. Em vez disso, Magalhães propôs chegar às Ilhas das Especiarias por uma rota ocidental, um feito que nunca foi realizado. Esperando que isto produzisse uma rota comercial comercialmente útil paraa Espanha , Carlos aprovou a expedição e forneceu a maior parte do financiamento.

Em 10 de agosto de 1519, os cinco navios sob o comando de Magalhães partiram de Sevilha e desceram o rio Guadalquivir até Sanlúcar de Barrameda, na foz do rio. Lá eles permaneceram por mais de cinco semanas. A frota deixou a Espanha em 20 de setembro de 1519, navegando para oeste através do Atlântico em direção à América do Sul. A frota de Magalhães consistia em cinco navios, transportando suprimentos para dois anos de viagem. A tripulação era composta por cerca de 270 homens. A maioria eram espanhóis, mas cerca de 40 eram portugueses.

Em 13 de dezembro, a frota chegou ao Rio de Janeiro, Brasil . Embora nominalmente território português, não mantinham ali qualquer assentamento permanente na época. Não vendo nenhum navio português no porto, Magalhães sabia que seria seguro parar.

A frota passou 13 dias no Rio, durante os quais consertaram seus navios, estocaram água e alimentos (como inhame, mandioca e abacaxi) e interagiram com a população local. A expedição trouxe consigo uma grande quantidade de bugigangas destinadas ao comércio, como espelhos, pentes, facas e sinos. Os habitantes locais trocavam prontamente alimentos e produtos locais (como penas de papagaio) por esses itens. A tripulação também descobriu que poderia comprar favores sexuais das mulheres locais. O historiador Ian Cameron descreveu o tempo da tripulação no Rio como "uma saturnália de festas e amores".

No dia 27 de dezembro, a frota partiu do Rio de Janeiro. Pigafetta escreveu que os nativos ficaram desapontados ao vê-los partir e que alguns os seguiram em canoas tentando convencê-los a ficar.

Após três meses de buscas (incluindo uma falsa largada no estuário do Río de la Plata), as condições climáticas obrigaram a frota a interromper as buscas para esperar o inverno. Eles encontraram um porto natural protegido no porto de Saint Julian e lá permaneceram por cinco meses. Pouco depois de desembarcar em St. Julian, houve uma tentativa de motim liderada pelos capitães espanhóis Juan de Cartagena, Gaspar de Quesada e Luis de Mendoza. Magalhães mal conseguiu reprimir o motim, apesar de a certa altura ter perdido o controle de três de seus cinco navios para os amotinados. Mendoza foi morto durante o conflito e Magalhães condenou Quesada e Cartagena à decapitação e abandono, respectivamente. Conspiradores de nível inferior foram obrigados a realizar trabalhos forçados acorrentados durante o inverno, mas depois foram libertados.

Durante o inverno, um dos navios da frota, o Santiago, perdeu-se numa tempestade enquanto pesquisava águas próximas, embora nenhum homem tenha morrido. Após o inverno, a frota retomou a busca por uma passagem para o Pacífico em outubro de 1520. Três dias depois, encontraram uma baía que os levou a um estreito, hoje conhecido como Estreito de Magalhães, que lhes permitiu a passagem para o Pacífico. Ao explorar o estreito, um dos quatro navios restantes, o San Antonio, abandonou a frota, retornando para o leste, para a Espanha. A frota chegou ao Pacífico no final de Novembro de 1520. Com base na compreensão incompleta da geografia mundial da época, Magalhães esperava uma curta viagem para a Ásia, talvez demorando apenas três ou quatro dias. Na verdade, a travessia do Pacífico durou três meses e vinte dias. A longa viagem esgotou o suprimento de comida e água, e cerca de 30 homens morreram, a maioria de escorbuto. O próprio Magalhães permaneceu saudável, talvez devido ao seu fornecimento pessoal de marmelo em conserva.

Em 6 de março de 1521, a frota exausta chegou à ilha de Guam e foi recebida pelos nativos Chamorro que embarcaram nos navios e levaram itens como cordame, facas e um barco de navio. O povo Chamorro pode ter pensado que estava participando de uma troca comercial (pois já havia fornecido alguns suprimentos à frota), mas a tripulação interpretou suas ações como roubo. Magalhães enviou um grupo de ataque a terra para retaliar, matando vários homens Chamorro, queimando suas casas e recuperando os bens “roubados”.

No dia 16 de março, a frota chegou às Filipinas , onde permaneceria por um mês e meio. Magalhães fez amizade com líderes locais na ilha de Limasawa e, em 31 de março, realizou a primeira missa nas Filipinas, plantando uma cruz na colina mais alta da ilha. Magalhães começou a converter os habitantes locais ao cristianismo . A maioria aceitou prontamente a nova religião, mas a ilha de Mactan resistiu.

Em 27 de abril, Magalhães e membros de sua tripulação tentaram subjugar os nativos de Mactan pela força, mas na batalha que se seguiu, os europeus foram derrotados e Magalhães foi morto por Lapulapu, um chefe nativo de Mactan.

Após a sua morte, Magalhães foi inicialmente sucedido pelos co-comandantes Juan Serrano e Duarte Barbosa (com uma série de outros oficiais liderando posteriormente). A frota deixou as Filipinas (após uma traição sangrenta do ex-aliado Rajah Humabon) e finalmente dirigiu-se para as Molucas em novembro de 1521. Carregados de especiarias, tentaram zarpar para Espanha em dezembro, mas descobriram que apenas um dos restantes dois navios, o Victoria, estavam em condições de navegar.

O Victoria partiu pela rota do Oceano Índico para casa em 21 de dezembro de 1521, comandado por Juan Sebastián Elcano. Em 6 de maio de 1522, o Victoria dobrou o Cabo da Boa Esperança, tendo apenas arroz como ração.

Vinte tripulantes morreram de fome em 9 de julho de 1522, quando Elcano chegou ao Cabo Verde português em busca de provisões. A tripulação ficou surpresa ao saber que a data era na verdade 10 de julho de 1522, pois haviam registrado todos os dias da viagem de três anos sem omissão. No início, eles não tiveram problemas para fazer compras, usando a história de que estavam voltando das Américas para a Espanha. No entanto, os portugueses detiveram 13 tripulantes após descobrirem que o Victoria transportava especiarias das Índias Orientais. O Victoria conseguiu escapar com sua carga de 26 toneladas de temperos (cravo e canela).

Em 6 de setembro de 1522, Elcano e o restante da tripulação da viagem de Magalhães chegaram a Sanlúcar de Barrameda, na Espanha, a bordo do Victoria, quase exatamente três anos após sua partida. Eles então navegaram rio acima até Sevilha e de lá por terra até Valladolid, onde compareceram perante o imperador. Quando o Victoria, o único navio sobrevivente e a menor nau da frota, retornou ao porto de partida após completar a primeira circunavegação da Terra, apenas 18 homens dos 270 homens originais estavam a bordo. Além dos europeus que retornaram, o Victoria tinha a bordo três molucanos que embarcaram em Tidore.

Magalhães tornou-se conhecido pela sua habilidade de navegação e tenacidade. A primeira circunavegação foi chamada de "a maior viagem marítima da Era dos Descobrimentos" e até mesmo "a viagem marítima mais importante já realizada". A apreciação das realizações de Magalhães pode ter sido reforçada ao longo do tempo pelo fracasso das expedições subsequentes que tentaram refazer a sua rota, começando com a expedição Loaísa em 1525 (que contou com Juan Sebastián Elcano como segundo em comando). A próxima expedição a completar com sucesso uma circunavegação, liderada por Francis Drake, não ocorreria até 1580, 58 anos após o retorno do Victoria.

Magalhães nomeou o Oceano Pacífico (que também foi frequentemente chamado de Mar de Magalhães em sua homenagem até o século XVIII) e empresta seu nome ao Estreito de Magalhães.

Embora Magalhães não tenha sobrevivido à viagem, recebeu mais reconhecimento pela expedição do que Elcano, pois foi Magalhães quem a iniciou, Portugal queria reconhecer um explorador português e a Espanha temia o nacionalismo basco.