Использовав по мере возможности скудные результаты амазонского путешествия и оправившись после болезни, Уоллес стал разрабатывать план нового путешествия в тропики, на этот раз в азиатские, именно на мало в то время исследованные острова Малайского архипелага. Теперь он уже не строил своих планов на шатком фундаменте продажи коллекций. Познакомившись с влиятельным уже в то время молодым профессором Томасом Гексли, Уоллес заинтересовал его своими планами, и Гексли удалось выхлопотать ему правительственную субсидию и рекомендации, сильно облегчившие его работу. Помимо этого финансовую помощь оказал ему богатый коллекционер Вильям Саундерс. В 1854 году Уоллес отправился в свое малайское путешествие, из которого вернулся лишь через 8 лет уже известным ученым, разделившим славу с самим Дарвином. Малайское путешествие Уоллеса сыграло решающую роль в формировании его научных взглядов и обогатило науку огромным количеством фактов.
Опишем сначала маршрут путешествия, что сделать не так-то просто, ибо последовательного маршрута в общепринятом смысле у Уоллеса не было: он, что называется, «колесил» по Малайскому архипелагу и исколесил его вдоль и поперек, подолгу останавливаясь в особенно интересных и добычливых местах и часто по нескольку раз посещая один и тот же остров. Прибыв в главный центр английского могущества в Юго-Восточной Азии – Сингапур, Уоллес совершил оттуда краткую экскурсию на Малайский полуостров и поднимался там на гору Офир. После этого он в конце 1854 г. направился на остров Калимантан, причем долгое время жил у английского губернатора княжества Саравак мистера Брука. На Калимантане Уоллес пробыл весь 1855 год, причем работа его шла необычайно плодотворно: было собрано до 2000 новых видов насекомых и птиц, были сделаны чрезвычайно обстоятельные наблюдения над жизнью орангутана, которые до сих пор фигурируют во всех описаниях этой обезьяны и считаются классическими. Наконец, в Сараваке же Уоллес приобрел двух помощников: малайского мальчика Али и молодого англичанина Чарлза Аллена, которые верой и правдой служили ему на протяжении его путешествия и немало способствовали его успеху. Распростившись с Сараваком, Уоллес вернулся в Сингапур, чтобы оттуда перебраться в восточный угол архипелага – сначала на острова Бали и Ломбок, а потом в Макасар на острове Сулавеси и, наконец, в самом конце 1856 года на далекий Аруанский архипелаг, населенный папуасами.
Пребывание на островах Ару было необычайно плодотворно – собраны тысячи ценнейших бабочек и райских птиц, произведены интереснейшие фаунистические и антропологические наблюдения. Интересно, что, по словам Уоллеса, вид аруанских лесов, резко отличающихся от джунглей индо-малайской части архипелага, воскресил в его памяти «полузабытые впечатления лесов экваториальной Америки».
Лишь в июле 1857 года путешественник вернулся в Макасар на Сулавеси, чтобы последующие три года посвятить изучению Молуккских островов, образующих переход между индо-малайской и австрало-малайской частями архипелага. Побывав на Амбоне и Тиморе, Уоллес поселился на небольшом островке Тернате, резиденции голландского губернатора молуккских и новогвинейских владений. Тернате славился здоровым климатом, и Уоллес нанял там на целых три года дом, который служил ему базой всех его последующих поездок: сюда он свозил собранные коллекции, здесь отдыхал и выздоравливал после изнурительных походов и приступов малярии. Из Тернате он ездил на близкий остров Джилоло, а в течение первой половины 1858 года совершил довольно неудачную и изнурительную поездку на пользовавшееся дурной славой западное побережье Новой Гвинеи. Вернувшись из Новой Гвинеи, Уоллес в течение 1859 года посетил остров Морских Разбойников (Баджан), побывал на Сулавеси, в Манадо (Венанг), снова на Амбоне и дважды посетил остров Серам. В январе 1860 года Уоллес послал Чарлза Аллена коллектировать на островок Мисоол, а сам объехал побережье островов Вайгео, у северо-западной оконечности Новой Гвинеи, посетив попутно Горам. В конце года оба путешественника съехались на своей тернатской базе. В 1861 году Уоллес отправил Аллена в длительную поездку на Новую Гвинею и различные мелкие не посещенные еще острова, затем на Калимантан и Яву, а сам, ликвидировав свою тернатскую базу, пустился в обратный путь, снова посетив Тимор и заехав на Яву и Суматру. В 1862 году он вернулся на родину.
За время своих восьмилетних скитаний по архипелагу Уоллес покрыл около 14 000 английских миль, использовав все способы путешествия: пешком, верхом, на пароходе, на благоустроенных малайских прау и китайских джонках, на утлых папуасских челнах с аутригером. Впрочем, он почти никогда не удалялся далеко от культурных центров, где благодаря своим рекомендациям пользовался содействием английских и голландских губернаторов и подвластных им туземных раджей; лишь на островах Ару и Вайгео и особенно на пустынном побережье населенной папуасами Новой Гвинеи ему приходилось полагаться на собственную бдительность.