Po niekoľkých rokoch práce železničného geodeta s bratom sa Wallaceov život zmenil, keď v roku 1847 stretol v Leicesteri Henryho Waltera Batesa.
Amazonka
Wallace a Bates diskutovali o myšlienke expedície do Amazonky. Plánovali pokryť náklady zaslaním vzoriek do Londýna, kde by ich agent predal za províziu. Tiež aby cestovatelia "zozbierali fakty na vyriešenie problému pôvodu druhov", ako sa Wallace vyjadril v liste Batesovi. Obaja priatelia, ktorí už boli skúsenými amatérskymi entomológmi, sa stretli v Londýne, aby sa pripravili na prehliadku juhoamerických rastlín a živočíchov v hlavných zbierkach.
Bates a Wallace vyplávali z Liverpoolu v apríli 1848 a do Pará (dnes Belém) dorazili koncom mája. Prvý rok sa usadili vo vile neďaleko mesta, kde zbierali vtáky a hmyz. Potom sa dohodli, že budú zbierať samostatne.
Wallace pokračoval v mapovaní Amazonky štyri roky, zbieral vzorky a robil si poznámky o národoch, jazykoch, geografii, flóre a faune. Dňa 12. júla 1852 sa Wallace vydal na loď Helen do Anglicka. Po dvadsiatich ôsmich dňoch na mori sa na lodi vznietil balzam v náklade a posádka bola nútená opustiť loď. Všetky exempláre, ktoré mal Wallace na lodi, teda väčšina jeho zbierky, sa stratili. Zachránil len časť svojho denníka a niekoľko náčrtov. Wallace a posádka strávili desať dní na otvorenom člne, kým ich vyzdvihla briga Jordeson.
Východná India
V rokoch 1854 až 1862, vo veku 31 až 39 rokov, Wallace cestoval po Holandskej východnej Indii (dnešná Malajzia a Indonézia), aby zbieral exempláre na predaj a študoval prírodu. Wallace nazbieral v Holandskej východnej Indii viac ako 125 000 exemplárov (len chrobákov bolo viac ako 80 000). Viac ako tisíc z nich predstavovalo pre vedu nové druhy.
Jeho pozorovania zreteľných zoologických rozdielov v úzkom prielive na súostroví ho viedli k návrhu zoogeografickej hranice, ktorá je dnes známa ako Wallaceova línia. Bali a Lombok boli dva ostrovy v súostroví, ktoré boli v najširšom mieste (28 km) od seba vzdialené len 17 míľ, mali približne rovnakú veľkosť a rovnaké podnebie, pôdu, nadmorskú výšku a aspekt. Napriek tomu sa ich flóra a fauna veľmi líšili.
"Na tomto súostroví existujú dve odlišné, pevne ohraničené fauny, ktoré sa od seba líšia rovnako ako fauny Afriky a Južnej Ameriky... a pritom na mape ani na povrchu ostrovov nie je nič, čo by označovalo ich hranice. Hraničná čiara prechádza medzi ostrovmi, ktoré sú k sebe bližšie ako ostatné patriace do tej istej skupiny. Domnievam sa, že západná časť je oddelenou časťou kontinentálnej Ázie, zatiaľ čo východná je fragmentárnym predĺžením bývalého západného pacifického kontinentu".
Zamýšľal sa nad tým, prečo sú zvieratá a rastliny na strane Bali ázijského typu, zatiaľ čo na strane Lomboku sú austrálskeho typu? To muselo znamenať, že západná skupina sa vyvinula zo spoločného západného kmeňa, zatiaľ čo východná skupina sa vyvinula zo spoločného východného kmeňa.
Počas skúmania súostrovia spresnil svoje myšlienky o evolúcii a získal slávny poznatok o prirodzenom výbere. V roku 1858 poslal Darwinovi článok, v ktorom načrtol svoju teóriu; ten bol spolu s opisom Darwinovej vlastnej teórie uverejnený v tom istom roku.
Zápisky z jeho štúdií a dobrodružstiev, ktoré tam zažil, boli napokon publikované v roku 1869 pod názvom Malajské súostrovie. Stala sa jedným z najpopulárnejších prírodovedných cestopisov 19. storočia. Chválili ho Charles Darwin a Charles Lyell a ďalší, napríklad spisovateľ Joseph Conrad, ktorý ho nazval svojím "obľúbeným spoločníkom pri posteli".
