Po několika letech, kdy pracoval se svým bratrem jako železniční zeměměřič, se Wallaceův život změnil, když v roce 1847 potkal v Leicesteru Henryho Waltera Batese.
Amazonka
Wallace a Bates diskutovali o myšlence výpravy do Amazonie. Plánovali, že náklady pokryjí tím, že pošlou vzorky zpět do Londýna, kde je agent prodá za provizi. Také aby cestovatelé "shromáždili fakta k vyřešení problému původu druhů", jak napsal Wallace v dopise Batesovi. Oba přátelé, kteří již byli zkušenými amatérskými entomology, se sešli v Londýně, aby se připravili prohlídkou jihoamerických rostlin a živočichů v hlavních sbírkách.
Bates a Wallace vypluli z Liverpoolu v dubnu 1848 a koncem května dorazili do Pará (dnes Belém). První rok se usadili ve vile nedaleko města a věnovali se sběru ptáků a hmyzu. Poté se dohodli, že budou sbírat samostatně.
Wallace pokračoval v mapování Amazonie po čtyři roky, sbíral vzorky a dělal si poznámky o lidech, jazycích, geografii, flóře a fauně. Dne 12. července 1852 se Wallace vydal na palubě brigy Helen do Anglie. Po osmadvaceti dnech na moři se na lodi vznítil balzám v nákladu a posádka byla nucena loď opustit. Všechny exempláře, které měl Wallace na lodi, tedy většina jeho sbírky, byly ztraceny. Zachránil pouze část svého deníku a několik náčrtů. Wallace a posádka strávili deset dní na otevřeném člunu, než je vyzvedla briga Jordeson.
Východní Indie
V letech 1854 až 1862, kdy mu bylo 31 až 39 let, cestoval Wallace po Nizozemské východní Indii (dnešní Malajsie a Indonésie), aby sbíral vzorky na prodej a studoval přírodu. Wallace v Nizozemské východní Indii nasbíral více než 125 000 exemplářů (jen brouků nasbíral více než 80 000). Více než tisíc z nich představovalo pro vědu nové druhy.
Jeho pozorování zřetelných zoologických rozdílů v úzkém průlivu na souostroví vedlo k návrhu zoogeografické hranice, která je dnes známá jako Wallaceova linie. Bali a Lombok byly dva ostrovy v souostroví, které byly v nejširším místě (28 km) od sebe vzdáleny pouhých 17 mil, měly zhruba stejnou rozlohu a stejné klima, půdu, nadmořskou výšku i úhel pohledu. Přesto se jejich flóra a fauna tolik lišily.
"Na tomto souostroví existují dvě odlišné, pevně ohraničené fauny, které se liší stejně jako fauny Afriky a Jižní Ameriky... přesto není na mapě ani na povrchu ostrovů nic, co by vyznačovalo jejich hranice. Hraniční čára prochází mezi ostrovy, které jsou si blíže než ostatní ostrovy patřící do stejné skupiny. Domnívám se, že západní část je oddělenou částí kontinentální Asie, zatímco východní je fragmentárním prodloužením bývalého západního pacifického kontinentu".
Zajímalo ho, čím to je, že zvířata a rostliny na straně Bali jsou asijského typu, zatímco na straně Lomboku jsou australského typu? To muselo znamenat, že západní skupina se vyvinula ze společného západního kmene, zatímco východní skupina se vyvinula ze společného východního kmene.
Během svého objevování souostroví upřesnil své myšlenky o evoluci a dospěl ke svému slavnému poznatku o přírodním výběru. V roce 1858 poslal Darwinovi článek, v němž nastínil svou teorii; ten byl spolu s popisem Darwinovy vlastní teorie publikován v témže roce.
Zprávy o jeho studiích a dobrodružstvích, které tam zažil, byly nakonec publikovány v roce 1869 pod názvem Malajské souostroví. Stala se jedním z nejpopulárnějších přírodovědných cestopisů 19. století. Pochvalně se o něm vyjádřili Charles Darwin a Charles Lyell a další, například spisovatel Joseph Conrad, který jej označil za svého "oblíbeného společníka u postele".
