Then retracing his steps to the Zambesi again, he followed its course to its mouth on the east coast, thus for the first time crossing Africa from west to east.

In a second journey, on which he started in 1858, he commenced tracing the course of the river Shire, the most important affluent of the Zambesi, and in so doing arrived on the shores of Lake Nyassa in September 1859.
Meanwhile two explorers, Captain (afterwards Sir Richard) Burton and Captain Speke, had started from Zanzibar to discover a lake of which rumours had for a long time been heard, and in the following year succeeded in reaching Lake Tanganyika.

On their return Speke parted from Burton and took a route more to the north, from which he saw another great lake, which afterwards turned out to be the Victoria Nyanza.

In 1860, with another companion (Captain Grant), Speke returned to the Victoria Nyanza, and traced out its course.

On the north of it they found a great river trending to the north, which they followed as far as Gondokoro.