Стэнли гнал их вперед, поскольку хотел любой ценой превзойти дневные переходы всех своих предшественников. И действительно, его караван проходил вдень в среднем на четыре километра больше, но к январю 1875 года восемьдесят девять носильщиков сбежали, тридцать заболели, двадцать умерли. С припасами обходились более бережно, чем с людьми. Так, из путевых заметок читатели узнали о так называемом марше голода, когда люди не побрезговали протухшим мясом павшего слона, в то время как караван все еще вел с собой скот для убоя. В последнюю неделю января Стэнли вступил в первое из более чем тридцати сражений этого путешествия. Видимо, против него выступили две тысячи воинов-вататуру. Стэнли никогда не соглашался идти в обход, если мог пробить себе дорогу огнем... До озера дошло меньше половины личного состава экспедиции; остальные умерли от голода и болезней, погибли в стычках или просто убежали. Одной из первых жертв стал Эдуард Покок, Скончавшийся от лихорадки 17 января 1875 года. 27 февраля 1875 года караван прибыл в селение Кагейи на южном берегу Виктории (немного восточнее Мванзы того места, где побывал в 1858 году Спик). 8 марта 1875 года Стэнли, оставив основную часть экспедиции в Кагейи, пустился в плавание по озеру на собранной и спущенной на воду Леди Элис . Первые же дни плавания увенчались открытием большого юго-восточного залива озера, который Стэнли назвал именем Спика. Обогнув с запада крупный остров Укереве и оставив по левому борту соседний остров Укара, путешественник двинулся на север вдоль восточного берега Виктории, старательно отмечая на карте все извивы береговой линии; при этом он смог удостовериться в том, что среди притоков, которые озеро принимает с восточной стороны, нет ни одного сколько-нибудь значительного (о чем говорили и сведения, собранные Спиком). По прибытии к северному берегу, в Буганду, Стэнли нанес визит Мтесе и заручился его поддержкой, после чего продолжил свое плавание теперь уже в сопровождении целой флотилии пирог баганда. Следуя вдоль северного, а затем западного берега озера, он посетил устья Катонги и Кагеры; особенно заинтересовала его Кагера, по которой он поднялся на несколько километров, но не смог продвинуться дальше из-за слишком сильного течения. Стэнли убедился, что эта река превосходит по водоносности все прочие притоки Виктории и, следовательно, может претендовать на роль главного истока Нила. 5 мая он завершил объезд озера, снова прибыв в Кагейи, где узнал о смерти Баркера, последовавшей от лихорадки 27 апреля. В результате кругового плавания Стэнли по озеру Виктория была прослежена и положена на карту, хотя и не слишком точно, почти вся его береговая линия.
Неисследованным остался лишь юго-западный угол озера, срезанный Стэнли наискосок на обратном пути в Кагейи; кроме того, от внимания путешественника ускользнул большой северо-восточный залив Кави-рондо (узкий вход в него Стэнли принял за вершину сравнительно не глубоко вдающейся в сушу бухты, которая и значится в этом месте на его карте). Эти пробелы, разумеется, ничуть не умаляют значения плавания Стэнли, явившегося фундаментальным вкладом в решение нильской проблемы . Я не вышел за рамки поставленной мне задачи, писал Стэнли, а именно исследования южных истоков Нила и разрешения проблемы, оставшейся нерешенной Спиком и Грантом: является ли Виктория-Ньянза одним озером или состоит из пяти озер, как сообщали Ливингстон, Бёртон и др. Эта проблема теперь удовлетворительным образом решена, и Спику принадлежит вся честь открытия крупнейшего внутреннего моря на Африканском континенте, а также его главного притока, равно как и его стока. Я должен также сказать в похвалу ему, что он понял географию посещенных им стран лучше любого из тех, кто так настойчиво критиковал его гипотезу, и выражаю здесь мое восхищение этим гениальным географом, который на основании одних лишь сообщений туземцев впервые так мастерски наметил очертания Виктории-Ньянзы . Переправившись вместе со всеми своими людьми через озеро в Буганду, Стэнли провел там несколько месяцев, знакомясь со страной и готовясь к новому исследовательскому предприятию сухопутному путешествию на запад от Буганды, где, по рассказам местных жителей, находилось большое озеро Мута-Нзиге. Под сходными названиями (Лута-Нзиге, Мвутан-Нзиге) было известно открытое Бейкером озеро Альберт, и Стэнли не сомневался, что именно о нем и идет речь. Для охраны экспедиции Мтеса выделил вооруженный отряд, насчитывавший более двух тысяч человек. Поход начался в ноябре 1875 года. Поднявшись вверх по заболоченной долине Катонги и перейдя слабо выраженный в рельефе водораздел между нею и текущей на запад рекой Русанго, Стэнли увидел в начале января 1876 года далеко на северо-западе горный массив Рувензори огромную синюю массу, которая, как нам сказали, была великой горой в стране Гамбарагара . Путешественник дал этой горе имя Гордона Беннета, издателя Нью-Йорк геральд ; исконное африканское название ее, под которым она значится на современных картах, было ему тогда неизвестно. Высоту горы Стэнли определил примерно в 4300- 4600 метров над уровнем моря, т. е. несколько заниженно (высшая точка Рувензори 5109 метров). Он слышал о том, что на ее вершине часто виден снег, но не узнал о существовании у нее постоянной снеговой шапки.
Тот факт, что им был открыт третий по высоте горный массив Африки, обнаружился лишь значительно позднее. 11 января 1876 года экспедиция стала лагерем в полутора километрах от края плоскогорья, у подножия которого лежало Мута-Нзиге. Фактически это были два сообщающиеся между собой протокой озера, носящие на наших картах названия Эдуард и Джордж. Стэнли смог отчетливо разглядеть восточное, меньшее из них Джордж; он принял его за залив расположенного дальше к западу более обширного озера, по его представлениям, южного продолжения Альберт-Ньянзы Бейкера. Познакомиться с этими водами поближе путешественнику не удалось: вожди местных племен, встревоженные приближением войска баганда, наотрез отказались пустить непрошенных гостей в свои владения и были готовы в случае необходимости дать им вооруженный отпор. Стэнли вернулся в Буганду и оттуда в феврале 1876 года направился на юг, в Карагве, все еще надеясь достичь интересовавшего его озера другой, более южной дорогой. Однако и этот план не увенчался успехом: доступ в лежащие к западу от Карагве страны Мпороро и Руанду был чужестранцам категорически воспрещен. Что же касается озера Альберт, то Стэнли его даже не видел: он, видимо, решил, что голубое, расчерченное белыми барашками прибоя зеркало воды, которое он увидел с высоты горной цепи, и есть одна из бухт озера Альберт. Но это было озеро Эдуард, расположенное южнее, где не бывал еще ни один европеец. Попутно Стэнли сделал еще одно географическое открытие, ценность которого он так до конца и не понял: вершина, увиденная им в январе 1876 года к северу от его маршрута, была частью горного массива Рувензори, тех самых Лунных гор, которые так долго искали. Правитель Карагве Руманика, напротив, отнесся к Стэнли с тем же доброжелательством, с каким в свое время встретил Спика и Гранта, и путешественник воспользовался этой благоприятной обстановкой для исследования Кагеры. Он проследил меридионально ориентированный средний участок долины этой реки, заболоченный и усеянный многочисленными мелкими озерами, примерно до места слияния двух главных ее истоков Ньяварунгу и Рувуву. Собранные им сведения о том, что Кагера принимает с запада воды озера Аканьяру, были не вполне точны: Аканьяру не озеро, а река, главный правый приток Ньяварунгу (но в бассейнах Ньяварунгу и Аканьяру, действительно, имеются небольшие озера). Стэнли слышал также о существовании дальше к западу еще одного большого озера (имелось в виду Киву), но не смог выяснить, имеет ли оно связь с Кагерой и не является ли частью Мута-Нзиге. Из долины Кагеры Стэнли, как и Спик, видел на горизонте горы Мфумбиро (Вирунга) В конце марта 1876 года Стэнли покинул Карагве и месяцем позже вышел через северные и западные области Уньямвези к Уджиджи на озере Танганьика.
Вновь была собрана Леди Элис . Путешественник совершил круговое плавание по озеру Танганьика и установил точные контуры этого озера (34 тысячи квадратных километров), обойдя на судне и семь недель (июнь июль) его берега. Стэнли открыл залив на северо-западе озера, отделенный от основной его части длинным и узким полуостровом Убвари, который был назвал именем Бёртона. Вернувшись в Уджиджи, исследователь, убедился, что его неуемная энергия для других невыносима. Более сорока носильщиков сбежали, и среди них Калулу бывший мальчик-раб, которого ему подарили во время первого африканского путешествия. Калулу с тех пор всегда и везде сопровождал Стэнли, ходил в английскую школу и стал прототипом главного героя в книге Мой Калулу сентиментальной истории подростка, написанной, видимо, под влиянием идей Ливингстона, которые некоторое время занимали Стэнли. Кое-кого из бежавших удалось поймать, среди них оказался и Калулу, позже утонувший в Конго. Поскольку экспедиции угрожали оспа и дизентерия, Стэнли, не теряя времени, нанял новых носильщиков. Неожиданные результаты принесло исследование Лукуги. Стэнли проследил эту реку дальше, чем Камерон, и пришел к выводу, что тот ошибся, считая, что она дает сток водам Танганьики: русло Лукуги оказалось целиком закупорено наносами и занято папирусовым болотом с отдельными окнами стоячей воды. Только позднее выяснилось, что этот сток временно прекратился. Причиной последнего явления было образование в долине Лукуги в результате землетрясения, оползня или обвала естественной плотины, которую и видел Стэнли. Уровень Танганьики, превратившейся в бессточное озеро, в течение нескольких десятилетий (начиная по крайней мере с 1846 года) постепенно повышался. В 1878 году, через два года после посещения Танганьики Стэнли, озерные воды прорвали запруду и вновь стали стекать в Лукугу, что привело к быстрому понижению уровня озера. 4 сентября 1876 года Стэнли пересек озеро и от Танганьики двинулся вниз по долине реки Лвамы и через сорок один день дошел до ее устья она оказалась притоком Луалабы. Бледно-серый поток Луалабы шириной полтора километра изгибался с юга на северо-запад. Мой долг добраться по нему до моря, какие бы препятствия ни встали на моем пути . В конце октября 1876 года Стэнли прибыл в Ньянгве. Стэнли знал, что для осуществления этого намерения ему необходимо в первую очередь заручиться поддержкой арабско-суахилийских торговцев, распространивших свою власть по Луалабе до Ньянгве (примерно напротив сегодняшнего Кибомбо). Не испытывая в отличие от Ливингстона и Камерона недостатка в деньгах, он сравнительно легко заключил соглашение с Хамедом бен Мухаммедом, больше известным под именем Типпо-Тип, самым влиятельным охотником за рабами и добытчиком слоновой кости в этом районе.