對金錢和探險的渴望更勝於休養的華萊士，仍然在找尋萬秘之謎物種源起的答案，因此也需要更多生物學的資料。在英國十八個月的時間裏，他出版了兩本書：一本是前面提過的《亞馬遜河和涅格羅河遊記》，另一本篇幅較小，名為《亞馬遜的棕櫚樹及其用途》（Palm Trees of the Amazon and Their Uses）。這本書的內容出自那些從海倫號搶救回來的筆記。不過，這兩本書都沒讓他成名。
然後，他準備好重新出發從事蒐集的工作。基於科學的理由，以及做為一位自然史標本供應者的市場壓力，他選擇了熱帶島嶼。屬於他的噩運已經遠去，這個新選擇成為年輕的華萊士否極泰來的轉捩點。
他知道，島嶼通常是珍禽異獸的寶庫，尤其這群特別的島嶼更是。正如日後他寫道：經過持續出席動物與昆蟲學會的研討會，以及造訪大英博物館的昆蟲和鳥類部門後，我已經掌握足夠的資訊來判斷偉大的馬來群島是探險和自然蒐集家的勝地。
透過一位皇家地理學會的長輩伸出援手，這位窮小子很高興能取得半島與東方汽船公司的免費船票。這條船航經直布羅陀海峽（Gibraltar）到亞歷山卓港（Alexandria），改由陸路到蘇伊士（Suez）換乘另一艘船。一八五四年四月，抵達新加坡。
從新加坡到沙撈越
以新加坡為基地，華萊士在馬來大陸上蒐集了六個月的時間。這塊大陸的物種很豐富，但沒有他尋找的地理障礙和因而產生的陡峻分佈模式。十一月，他移師到位在婆羅洲西北區的沙撈越，展開隨後七年遊蕩於諸島的行程。
反省自己早期的粗心大意，和達爾文在加拉巴哥群島所犯的無知錯誤後，華萊士下定決心：到達東方之初始，我就已經打定主意，造訪過的每一個島嶼或特殊地區，定要保留某些動物一份完整的標本，以供返家後研究。因為我相信牠們是寶貴的材料，能讓我研究出動物在這個群島上之地理分佈，以及提示其他種種問題的解決之道。這些其他問題首要的當然是演化。
這時候的華萊士更聰明、更小心翼翼了，他除了在標本上註記產地外，並逐批裝載運回英國，不再囤積身邊。他沒料到那個大問題在他踏上歸途之前就會破解。事實上是破解了兩次，一次來自他本人，另一次則是達爾文。
沙撈越之行成果豐碩，不管在甲蟲、蝴蝶或鳥類都有相當的斬獲。華萊士獵到幾頭紅毛猩猩，並養了一隻成為孤兒的猩猩寶寶（雖然只存活一小段時間）：他遇過俗稱的黑蹼樹蛙（flying frog）；他花時間融入內地的迪雅克人；他寫了篇文章討論血緣相近物種的通則，隨即寄出。他還成為布魯克爵士歡度耶誕慶典時的座上賓，這位爵士是沙撈越的首長，老是喜歡找有智慧的英國年輕人聊上幾句。
野外工作停頓好一段時間，在婆羅洲的這一區待了一年多後，讓華萊士有家的感覺。但家是日後才可享受的奢侈品。因此華萊士決定離開，返回新加坡後再東遊，向船可及之遙遠境地、鮮為人知的群島東緣進軍。
他的足跡遠至峇里島，又跨海至龍目島。在那兒他發現這兩座相鄰島嶼上鳥類動物區系竟有令人訝異的極端差距。由那兒再上行到西里伯斯島的馬卡薩（Macassar）。
他在西里伯斯島停留了三個月。雖然人病了，天氣又陰溼多雨，加上馬卡薩周圍沒有茂密的森林，以及其他的重重困難，但他還是盡可能到處去蒐集。這場病可能又是瘧疾，雖然華萊士歸咎於污染的水。
西里伯斯島上的鳥類、哺乳類和昆蟲均有別於他在沙撈越所見。
有一種東南亞疣豬（babirusa）給他的印象特別深刻，學名為鹿豚（Babyrousa babyrussa），那是一種奇特的野豬。公豬的上犬齒就好像鹿角一樣，伸長並向上捲曲，穿過鼻子上的肉再彎回前額。華萊士並沒有因牠而連想到非洲疣豬，所以說：世界上已經完全沒有與此相類似的豬，東南亞疣豬能夠繼續存在，是歸因於完全的隔絕。牠如何進食？他想知道。牠如何運用那對外觀看起來怪異又不方便的長牙？什麼生長或行為因子能解釋這種解剖學上的變化？把這種有彎曲長牙的西里伯斯豬，看成是上帝的神來之筆的，華萊士不是唯一一個。
他也蒐集到兩種島上特產的犀鳥（hornbill）、一隻漂亮杜鵑和三隻鳥翼蝴蝶的標本。鳥翼蝴蝶是美麗至極的動物，展翅達七英吋，翅膀上妝點著白色和絲綢般黃色的斑點或條紋。他稍後記述：當我拿出網中第一隻蝴蝶，發現完好無缺時，激動得都會顫抖。對照攜帶的動物手冊後，他把這三個樣品歸入一個種（Ornithoptera remus）。但不完全相符，因此華萊士懷疑是西里伯斯島上特有之變種。除了這些以外，他有點失望。
與華萊士在婆羅洲和馬來西亞所見的相較，這裏的鳥類及昆蟲之多樣性似乎較為貧乏。他找不到擬啄木鳥、咬鵑、寬喙鴨和伯勞鳥。在寫給史迪芬的信中，華萊士抱怨道：整個屬、整個科的動物都缺席了，而且沒有其他物種來填補牠們的空缺。西里伯斯島於馬來群島幾近中點處孤立著，令人感興趣，可惜並不多產。
命運的轉折點：阿魯群島
氣候要開始轉變了。
十月、十一月間，馬卡薩吹的是溫暖乾燥、既穩定又強勁的東風，這時逐漸讓步給風向不穩定的輕風，以及不斷從西邊移入的暴雨雲，象徵著季節的更迭。有人警告華萊士，西風季風所帶來的傾盆大雨快來了，不可能進行蒐集工作。果然，一八五六年十二月，雨開始下了。
圍繞馬卡薩、綿延數英哩濱海平原上乾涸的水稻田，又再度灌滿水。除非撐船，或者沿田埂像走鋼絲般，否則郊區簡直寸步難行。有人告訴他，如果繼續滯留在南西里伯斯，將有一連五個月的時間要面對這種爛天氣。因此華萊士決定再度啟程，搭了一艘往東航向阿魯群島的馬來帆船，離開西里伯斯島。他說，與其困在屋內浪費數個月的光陰，不如跑在季風的前頭，讓它追不上。
華萊士聽過關於阿魯群島的傳聞。阿魯位在馬卡薩東方一千英哩處，是一小撮面積微不足道的島群。但因當地出產珍貴的生物商品，包括珍珠貝，乾海參以及天堂鳥皮和其他稀有物種，西里伯斯以海為生的土著：布吉人（Bugis ），對這個群島倒是如雷貫耳。
對布吉商人而言，出海到阿魯群島，就好比伊斯蘭教徒到麥加朝聖般，那可是一生中的大事啊！馬卡薩的商人，不管是布吉人還是移民來的華人，販售著從整個馬來地區來的各式各樣天然產物，如婆羅洲的白藤，佛羅勒斯島（Flores）和帝汶的檀香和蜜蠟，卡奔塔利亞灣（Gulf of Carpentaria）的海參，布魯島（Bouru）的玉樹油，甚至是米和咖啡等大宗貨物。
華萊士在這趟旅程過後數年寫道：但比所有這些更重要的是，到阿魯群島的貿易。那是位在新幾內亞西南近海的島群，而島上產物幾乎都是經土著的船運到馬卡薩來。對布吉人而言，阿魯群島是他們想像中最遠的境地。
華萊士補充道：這些島遠離所有歐洲人的貿易線，只有一些野蠻人，一身黑皮膚和一臉怪相。他們尚未引起那些高度文明化的民族窮奢極慾的興趣。這裏出產的珍珠、珍珠母貝和玳瑁殼被運往歐洲，而燕窩和海參則祭了華人的五臟廟。比起多數維多莉亞時代的旅行家，華萊士比較能對他造訪之地的土人感同身受，甚至對他稱之為黑皮膚、頭長得一臉怪相之野蠻人也是如此。但這方面他並不是完美無缺的，他的話只是反應了當時的時代背景。
這些黑皮膚和頭長得一臉怪相之野蠻人，實際上是新幾內亞濱海地區的巴布亞人（Papuans）移居的，那兒距阿魯群島約一百英哩。是不是野蠻人呢？整個馬來群島的東緣，從西里伯斯到更偏遠的島嶼，例如濟羅羅島（Gilolo）、布魯島、帝汶島、斯蘭島（Seram）、班達島和凱島（Ke），土著都是清一色的馬來人，而不是巴布亞人。換句話說，這些島上的住民特徵都是褐色皮膚、清瘦體型和直髮。阿魯群島竟然出現巴布亞人及豔麗的鳥皮和珍珠貝，暗示著這群不起眼的島嶼很不尋常。
十二月或是次年一月間，季風起，正是順風航往阿魯的好時節。要到七月或八月，才能從阿魯乘風返航。由於馬來帆船不擅迎風航行，因此若在其他時間，這段航程不是危險，而是根本不可能。華萊士補充說：這交易很早以前就有了。最早的、林奈所知道的兩種天堂鳥，就是透過這個管道帶來的。這兩種討論中的天堂鳥，體型較小。顏色鮮紅的一種俗稱為王風鳥（king bird of paradise，學名是Cicinnurus regius）；體型較大的則是另一種（Paradisaea apoda，林奈原來的拼字做了些許修正）。
華萊士本身也算是個生意人，兼具這種身份的博物學家當然很敏銳的盯上這些奇珍異種。對那些向史迪芬購買蒐集品的英國富有收藏家而言，一件完美的天堂鳥王標本，價值勝過地球上任何鳥類或昆蟲。
但並不是所有的布吉商人都敢做阿魯朝聖之行。華萊士寫道：
任何人只要完成這趟航程，就會被尊為業界之泰斗。但對多數人而言，那只是畢生未酬的壯志之一而已。我自己曾經夢想，但不敢預期能到這個東方之終極神秘遠方。當我發現夢想真能實現的時候，憑藉著勇氣，在一千英哩的航程中，把自己的性命交給馬來帆船，以及要相處六、七個月的化外商人和兇惡的野蠻人。
做這件事時，我自己有點像學校的學生，到一個景緻新鮮、奇特和絕妙的地方，而第一次被允許下公共馬車到外面遊玩的那種感覺。
他真的把性命交給了馬來帆船！
這種船是雙桅的木製貨船，形狀與中國帆船相仿，艙房以竹為材料，用白藤捆緊，頂蓋鋪上棕櫚。這一趟，海神們對華萊士友善了些，沒有把海倫號和喬德森號上的待遇再加諸他身上。一八五七年一月的第二週，他平安抵達阿魯群島。
只有極少數的自然學家、屈指可數的歐洲人，曾經親眼見識那個地方。而華萊士終其馬來之行，也沒再往更東邊去。
就多種意義上來看，阿魯是他生命的轉折點。