Inspirado pelas crônicas de naturalistas viajantes precedentes incluindo Alexander von Humboldt, Charles Darwin e William Henry Edwards, Wallace decidiu que ele também queria viajar para o exterior como naturalista. Em 1848 Wallace e Henry Bates partiram para o Brasil a bordo do Mischief. Sua intenção era coletar insetos e outros espécimes animais na Floresta Amazônica e vendê-los a colecionadores na Inglaterra, a venda de coleções era uma fonte de renda para custear as expedições. Também esperavam juntar evidências da transmutação das espécies. Wallace e Bates passaram a maior parte de seu primeiro ano coletando espécimes próximo a Belém do Pará, quando exploraram o interior separadamente, encontrando-se por ocasião para discutir seus achados. Em 1849, tiveram a breve companhia de um outro jovem explorador, o botânico Richard Spruce, junto com o irmão mais novo de Wallace, Herbert. Herbert partiu logo em seguida (falecendo dois dias depois de febre amarela), mas Spruce, assim como Bates, passaria quase dez anos coletando na América do Sul.
     Wallace continuou cartografando o Rio Negro por quatro anos, coletando espécimes e tomando notas acerca dos povos e línguas que encontrou bem como a geografia, flora e fauna. Em 12 de julho de 1852, Wallace embarcou rumo ao Reino Unido no brigue Helen. Após vinte e oito dias ao mar, o bálsamo na carga do navio pegou fogo e a tripulação foi forçada a abandona-lo. A coleção inteira que Wallace levava foi perdida. Pôde apenas salvar parte de seu diário e uns poucos esboços. Porém uma pequena parte de seu material ficou retida no porto de Manaus, esta se salvou. Wallace e sua tripulação
passaram dez dias num barco aberto antes de serem resgatados pelo brigue Jordeson, que estava viajando de Cuba para Londres. As condições no Jordeson foram tensas por causa dos passageiros inesperados, mas após uma viagem difícil com uma alimentação deficiente o navio finalmente chegou ao seu destino em 1 de outubro de 1852.
     Após seu retorno ao Reino Unido, Wallace passou dezoito meses em Londres vivendo do pagamento do seguro de sua coleção perdida e vendendo o que sobrou. Durante esse período, apesar de ter perdido quase todas as suas anotações de sua expedição à América do Sul, ele escreveu seis ensaios (os quais incluíram "On the Monkeys of the Amazon") e dois livros: "Palm Trees of the Amazon and Their Uses" e "Travels on the Amazon" (Palmeiras da Amazônia e seus usos e Viagens na Amazônia). Também firmou contato com inúmeros outros naturalistas britânicos – mais significantemente, Darwin. De 1854 a 1862, de 31 aos 39 anos de idade, Wallace viajou para a Arquipélago Malaio ou Índias Orientais (agora Malásia e Indonésia), afim de coletar espécimes para vender e estudar a natureza. Suas observações das marcantes diferenças zoológicas através do estreito no arquipélago levaram-no a propor a fronteira biogeográfica atualmente conhecida como a Linha de Wallace. Wallace coletou mais de 125.000 espécimes no Arquipélago Malaio (só de besouros mais de 80.000), sendo que mil representavam espécies novas para a ciência. Uma de suas mais bem conhecidas descrições de espécies durante sua viagem é a do sapo que desliza em árvores, Rhacophorus nigropalmatus, conhecido como o sapo-voador-de-wallace. Enquanto ele explorava o arquipélago, refinou seus pensamentos acerca da evolução e teve sua famosa concepção da seleção natural. Descrições de seus estudos e aventuras foram eventualmente publicadas em 1869 como "The Malay Archipelago", que se tornou um dos mais populares diários de exploração científica do século XIX, mantido continuamente à venda por sua editora inicial (Macmillan) até a segunda década do século XX. A publicação foi elogiada por cientistas tais como Darwin (a quem o livro foi dedicado), e Charles Lyell, e por não-cientistas, tais como o romancista Joseph Conrad, que chamou o livro de seu companheiro de cabeceira favorito e o usou como fonte de informações para vários de seus romances, especialmente Lord Jim.