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