Луалаба, истоки которой находятся далеко на юге, была пройдена Ливингстоном вплоть до Ньянгве, расположенного почти в центре континента, раскинувшегося между Атлантическим и Индийским океанами, примерно в четырех градусах к югу от экватора. Ливингстон так и не смог найти спутников, чтобы исследовать реку дальше на север. Даже наиболее отчаянный и жестокий работорговец того времени по имени Типпу Тип, живший в Ньянгве, сначала отказался присоединиться к нему. Типпу Тип, араб по происхождению, хитростью и насилием сколотил огромное состояние и приобрел значительную власть в Центральной Африке. Он вступал в союз с одним негритянским племенем против другого, предлагая помощь в битве. Выжившие враги становились его рабами. Он забирал их слоновую кость, а затем поворачивал оружие на победителей и обращался с ними точно так же. В результате он получал одновременно «белое» и «черное» золото по цене боеприпасов для мушкетов своих людей, поэтому его прибыли были огромны.
Услышав о том, что Стэнли собирается отправиться на север, Типпу Тип через некоторое время согласился сопровождать его с семью или восемью сотнями своих людей в течение двух месяцев за вознаграждение в пять тысяч долларов. Они отправились в путь 5 ноября 1876 года. Через две недели джунгли стали слишком плотными для людей, которые несли сборные секции «Леди Алисы», поэтому Стэнли спустил судно на воду и продолжал путешествие по реке, в то время как остальные шли вдоль берега.
В первые дни они миновали лишь заброшенные деревни; жители разбегались при приближении белых людей и Типпу Типа, оставляя за собой свежие черепа и обглоданные человеческие кости как доказательство своего каннибализма. Через две недели экспедиция подверглась открытому нападению. Затем в течение месяца они с боями продвигались вперед. Рождество они встретили примерно на полпути между Ньянгве и серией из семи водопадов, которые теперь называются водопадами Стэнли и отмечают начало бассейна реки Конго. Разразилась эпидемия оспы, погубившая сорок пять человек и еще многих лишившая способности передвигаться самостоятельно. Они были посланы назад вместе с отрядами Типпу Типа еще до начала следующего года. Затем, погрузившись на «Леди Алису» и флотилию долбленых каноэ, захваченных у туземцев, Стэнли, Фрэнсис Покок и более двухсот выживших занзибарцев продолжили экспедицию.
Рассказ о походе Стэнли, составленный в виде выдержек из его дневников, скрупулезно заполняемых в каждом путешествии, является нашим единственным источником информации об этом периоде. Он был поражен почти всеобщей враждебностью племен, населявших эту часть Африки. По мнению Стэнли, эта враждебность объяснялась тем, что дикари рассматривали его отряд как двуногую дичь, пригодную для еды (его история способствовала созданию в Англии и Соединенных Штатах расхожего мнения, что все африканцы являются каннибалами). К февралю 1887 года, когда Стэнли вступил во владения сравнительно цивилизованного племени басоко, делавшего резных идолов из слоновой кости, красочные деревянные маски и имевшего железные орудия, он выдержал двадцать восемь стычек с туземцами, потеряв убитыми тридцать три человека. Практически все были ранены, кроме самого Стэнли, который думал, что он родился в рубашке. Битва с племенем басоко была одной из тяжелейших, и ее описание служит хорошим примером авторского стиля Стэнли. Он рассказывает о том, как поставил свою флотилию на якорь посреди широкой реки, чтобы отразить атаку флота вражеских каноэ.
«Пятьдесят четыре туземных судна! Атаку возглавляет каноэ поистине чудовищных размеров с двумя рядами коротких весел, по сорок человек с каждого борта — их тела раскачиваются в унисон с нестройным варварским хором, мощные гребки вспенивают воду. На платформе, установленной на носу, стоят десять превосходных молодых воинов в ярких головных уборах из желтых, пурпурных и серых перьев; на корме восемь человек с длинными веслами, чьи верхушки украшены шариками из слоновой кости, правят этим зловещим судном. На каждой голове покачивается корона из перьев, на обнаженных руках сияют белые костяные браслеты. Уханье больших барабанов, дикий вой костяных рогов и пронзительное песнопение, издаваемое двумя тысячами человеческих глоток, отнюдь не успокаивает наши нервы и не укрепляет нашу уверенность».