Караван растянулся более чем на километр. Медная проволока, ситец, мешки, полные бисера, раковин каури и провизии, ящики со снаряжением, а также разобранный, достигавший двенадцатиметровой длины бот из кедрового дерева "Леди Элис" - все это несли на своих плечах носильщики. Стэнли гнал их вперед, поскольку хотел любой ценой превзойти дневные переходы всех своих предшественников. И действительно, его караван проходил в день в среднем на четыре километра больше, но к январю 1875 года восемьдесят девять носильщиков сбежали, тридцать заболели, двадцать умерли. С припасами обходились более бережно, чем с людьми. Так, из путевых заметок читатели узнали о так называемом марше голода, когда люди не побрезговали протухшим мясом павшего слона, в то время как караван все еще вел с собой скот для убоя.
В последнюю неделю января Стэнли вступил в первое из более чем тридцати сражений этого путешествия. Видимо, против него выступили две тысячи воинов-вататуру. Стэнли никогда не соглашался идти в обход, если мог пробить себе дорогу огнем...
До озера дошло меньше половины личного состава экспедиции; остальные умерли от голода и болезней, погибли в стычках или просто убежали. Одной из первых жертв стал Эдуард Покок, скончавшийся от лихорадки 17 января 1875 года.
27 февраля 1875 года караван прибыл в селение Кагейи на южном берегу Виктории (немного восточнее Мванзы - того места, где побывал в 1858 году Спик).
8 марта 1875 года Стэнли, оставив основную часть экспедиции в Кагейи, пустился в плавание по озеру на собранной и спущенной на воду "Леди Элис". Первые же дни плавания увенчались открытием большого юго-восточного залива озера, который Стэнли назвал именем Спика. Обогнув с запада крупный остров Укереве и оставив по левому борту соседний остров Укара, путешественник двинулся на север вдоль восточного берега Виктории, старательно отмечая на карте все извивы береговой линии; при этом он смог удостовериться в том, что среди притоков, которые озеро принимает с восточной стороны, нет ни одного сколько-нибудь значительного (о чем говорили и сведения, собранные Спиком). По прибытии к северному берегу, в Буганду, Стэнли нанес визит Мтесе и заручился его поддержкой, после чего продолжил свое плавание - теперь уже в сопровождении целой флотилии пирог баганда. Следуя вдоль северного, а затем западного берега озера, он посетил устья Катонги и Кагеры; особенно заинтересовала его Кагера, по которой он поднялся на несколько километров, но не смог продвинуться дальше из-за слишком сильного течения. Стэнли убедился, что эта река превосходит по водоносности все прочие притоки Виктории и, следовательно, может претендовать на роль главного истока Нила. 5 мая он завершил объезд озера, снова прибыв в Кагейи, где узнал о смерти Баркера, последовавшей от лихорадки 27 апреля.
В результате кругового плавания Стэнли по озеру Виктория была прослежена и положена на карту, хотя и не слишком точно, почти вся его береговая линия. Неисследованным остался лишь юго-западный угол озера, "срезанный" Стэнли наискосок на обратном пути в Кагейи; кроме того, от внимания путешественника ускользнул большой северо-восточный залив Кавирондо (узкий вход в него Стэнли принял за вершину сравнительно не глубоко вдающейся в сушу бухты, которая и значится в этом месте на его карте). Эти пробелы, разумеется, ничуть не умаляют значения плавания Стэнли, явившегося фундаментальным вкладом в решение "нильской проблемы".