Мтеза снова принял Стэнли и его спутников как самых дорогих друзей. В это время он готовился к войне с одним возмутившимся против него племенем и просил Стэнли сопутствовать ему в походе. Для этой войны Мтеза собрал до 150 тысяч войска, но ничего не мог поделать с бунтовщиками, засевшими на одном из островов и упорно выдерживавшими нападения, пока не построили по совету Стэнли невиданного в Африке судна, приведшего в ужас непокорных и заставившего их подчиниться Мтезе. В благодарность за помощь Мтеза оказал всяческое содействие отправлению Стэнли к озеру Мута-Нциге и дал ему значительный отряд войска для защиты при прохождении через владения Униоро, другого сильного государства Центральной Африки, владетель которого отличался крайней враждебностью к чужеземцам. Благодаря отряду угандцев Стэнли прошел через владения Униоро беспрепятственно, но везде встречал пустые селения, оставленные жителями, не пожелавшими вступать в какие бы то ни было сношения с экспедицией. На озере Мута-Нциге население также встретило экспедицию враждебно. Здесь Стэнли пришлось уже встретиться с ненавистью к белым. Дело в том, что Униоро, а также некоторые другие страны Центральной Африки, лежавшие на его пути, уже граничили с областями, которые в то время покорили и присоединили к Египту сподвижники знаменитого Гордона, в особенности Эмин-паша, губернатор Экваториальной провинции. Стэнли был встречен здесь как враг, и население рыцарски предупредило его, чтоб он приготовился выдержать нападение. Отряд угандцев, сопровождавший Стэнли, был испуган этим объявлением войны и решил отступить. Напрасно Стэнли протестовал против этого решения и грозил начальнику отряда гневом Мтезы. Угандцы на другой же день пошли назад, и Стэнли вынужден был следовать за ними. Выйдя из страны Униоро, Стэнли отделился от угандцев и пошел к Нил-Александре. Здесь к нему пришло письмо от Мтезы, который страшно возмутился трусостью начальника своего отряда, заключил его в тюрьму и умолял Стэнли вернуться и взять у него хоть целую армию для своих целей. Но Стэнли в это время пользовался уже благоволением другого африканского государя, так что помощь Мтезы ему была не нужна. Нил-Александра, или Кагера, был в то время совершенно неизвестною рекою, и Стэнли решил обследовать его. Здесь лежало негритянское царство Карагуэ, управляемое идеальным африканским государем Руманикой. Это был чрезвычайно добрый человек, который не только встретил Стэнли с полным радушием, но и сам увлекся исследованиями путешественника. Он собирал целые географические конгрессы из сведущих африканцев и вообще оказывал работам Стэнли всяческое содействие. Благодаря помощи Руманики Стэнли мог определить, что Нил-Александра есть самый южный приток озера Виктория, а следовательно, и самый верхний исток Нила.
Решив этот капитальный географический вопрос, Стэнли задумал идти к югу, чтобы докончить начатые покойным Ливингстоном исследования реки Луалабы. По дороге к озеру Танганьика ему пришлось проходить через владения известного уже Мирамбо. Слава Стэнли в Центральной Африке была в это время так велика, что Мирамбо, который имел полную возможность со своей громадной армией, вооруженной ружьями, раздавить экспедицию и тем отомстить Стэнли за его участие в нападении на него, Мирамбо, во время первого путешествия, послал к Стэнли спросить, продолжает ли он питать к нему, Мирамбо, враждебные чувства или желает быть его другом. Понятно, что Стэнли предпочел дружеские отношения, и между путешественником и грозой Центральной Африки был заключен союз крови.
27 мая 1876 года, то есть через полтора года по выступлении из Занзибара, Стэнли снова был в Уджиджи, на берегу озера Танганьика, придя сюда теперь совершенно иным путем, нежели в первое путешествие. Оставив в Уджиджи большую часть своего каравана, Стэнли объехал Танганьику. Озеро это замечательно необыкновенно быстрым поднятием своих вод. Когда Стэнли был в Уджиджи в 1871 году, он видел здесь на базарной площади три пальмы, которые в 1876 году оказались уже в озере, на расстоянии ста футов от берега. И такие же изменения Стэнли нашел повсюду. На своей лодке «Lady Alice» он исследовал значительную часть озера, и теперь оно из совершенно неведомого ранее превратилось в одно из наиболее известных мест Центральной Африки подобно другому громадному водному пространству той же части Африки — озеру Виктория.