Из Угого Стэнли повернул на север, к озеру Виктория. На этом пути самые тяжелые испытания экспедиции пришлось вынести в стране Итуру. Жители отнеслись враждебно к экспедиции с первого же момента вступления Стэнли в их область, и эта враждебность все увеличивалась по мере дальнейшего пути. Туземцы отказывались давать проводников, не продавали провизии, наконец предательски зарезали двух носильщиков. Стэнли старался до последней возможности сохранять мирные отношения с туземцами, но это оказалось невозможным. Огромные толпы напали на караван и осыпали его стрелами. Стэнли вынужден был пустить в ход оружие. Два дня пришлось биться с храбрыми дикарями почти грудь в грудь. После этого поднялась вся страна и против маленького отряда Стэнли началась настоящая война. Война эта стоила экспедиции 53 человек, и только смелость Стэнли, неожиданно обнаруженные им стратегические таланты да единодушие каравана, готового идти на смерть за своим вождем, дали возможность экспедиции пробиться через неприятельские полчища, сражаясь непрерывно в течение нескольких дней.
С такими приключениями Стэнли дошел через два с половиной месяца по выступлении из Занзибара до озера Виктория. В составе экспедиции к этому времени недоставало уже более 160 человек, из которых половина дезертировала, а остальные были убиты или умерли от болезней и истощения. Вся экспедиция была страшно измучена; половина людей состояла из больных. Туземный начальник Кагегии, городка на берегу Виктории, принял экспедицию самым радушным образом, и она имела возможность теперь спокойно отдохнуть. Сам Стэнли, однако, не думал об отдыхе. Он приказал спустить на воду свою лодку «Lady Alice» и с одиннадцатью людьми отправился исследовать Викторию.
Плавание по озеру оказалось крайне трудным. Бурное озеро-море готово было каждую минуту поглотить утлое суденышко. Но это было еще самым легким из бедствий. Гораздо больше беспокойств доставляла неприязненность населения. Всякий раз, как только Стэнли высаживался на берег, чтобы запастись провизией или отдохнуть, на него нападали вооруженные дикари, на озере постоянно приходилось сталкиваться с пиратами. Однажды на «Lady Alice» напала целая флотилия пирог, которую удалось отразить только благодаря огнестрельному оружию. В таком положении постоянной тревоги путешественники пробыли три недели. Вдруг все это совершенно исчезло, словно по волшебству. Вместо враждебных лиц, вооруженных воинов и туч стрел наших путников стали встречать радостные лица, дружественные приветствия и самое радушное гостеприимство. Оказалось, что Стэнли попал в королевство Уганда, управляемое могущественным Мтезой.