Kolejne miesiące spędził w Bugandzie, po czym rozpoczął następny etap swojej wyprawy, kierując się drogą lądową na poszukiwanie jeziora Muta Nzige, o którym opowiadali mu mieszkańcy. Sam podróżnik był przekonany, że jest to odkryte przez Bakera Jezioro Alberta. Karawana, zaopatrzona w oddział zbrojny liczący ponad 2000 ludzi, wyszła z Bugandy w listopadzie i przemierzając błotnistą Katongę, odkryła trzeci pod względem wysokości masyw górski – Ruwenzori. Podróżnik błędnie szacował jego wysokość na 4300–4600 m. W rzeczywistości wynosi ona w najwyższym punkcie 5109 m. Masyw został nazwany nazwiskiem Gordona Benneta, wydawcy „New York Herald”. Afrykańska i do dziś obowiązująca nazwa nie była znana Stanleyowi.
11 stycznia 1876 r. wyprawa dotarła do skraju wyżyny, u podnóża której leżało Jezioro Muta-Nzige, zwane dziś Jeziorami Alberta i Jerzego. W istocie były to dwa połączone kanałem jeziora, których nie udało się zbadać podróżnikowi, ponieważ wodzowie miejscowych plemion stanowczo sprzeciwili się wpuszczeniu na swoje tereny nieproszonych gości. Stanley wrócił zatem do Bugandy i stąd w lutym skierował się na południe, mając wciąż nadzieję na dotarcie do jeziora inną drogą.