This did not look very hopeful; but, after a long wait, the chief lent his new friend "Stamlee" enough canoes to carry half his camp, though they proved to be the worst and oldest of all his fleet. The canoes of the Nyanza were made of thin boards, laced together with cane fibre, and the seams were caulked with a kind of putty made of pounded banana stalk. Stanley told some of his followers to patch up Lukongeh's canoes; and then, on June 20, he started for Refuge Island, with 150 men and half his stores.

Their first night's camp was to be on an islet, and they had to push on after dusk to reach it. Suddenly Stanley heard the desperate cry, "Bring the boat, master; we're sinking!" Hurrying to the spot, he found that a canoe had sunk, and her crew were struggling in the water. The rotten cane fibre had given way, and a heavy box of ammunition had fallen through the bottom, and she had filled in a moment.

Scarcely had Stanley picked up the men, when the same cry was heard a few hundred yards away, "The boat, master! the boat!" The lacing of a second canoe had ripped open, and her crew could not bale her out fast enough to keep her afloat. These also were taken aboard the Lady Alice, who was now loaded down to her gunwale, when another, and yet another cry for help came ringing over the water. Telling the canoe-men to bale for their lives, Stanley hurried the boat towards the island. It seemed as if they would never be there; but at last she grounded, and after being speedily emptied, she was raced back to the rescue.

It was pitch dark when they returned to the sinking canoes; and to see what was going on, Stanley had to light, one by one, the leaves of a book he had brought to read on the way. Thus fumbling their way from sound to sound, they managed to save all the lives; but they lost five canoes, five rifles, some ammunition, and 1200 lbs. of grain.

On reaching Refuge Island, Stanley sent back for the rest of his camp; and in this same manner he moved all his men and stores to Mahyiga, an isle close to Bumbiré. Here they were joined by a large search party, sent in canoes by the anxious Mtesa. Magassa had gone as far as Bumbiré, where the natives told him the story that the Lady Alice  had been lost in the Nyanza during a storm. They also gave up the oars, and said these were all that remained of the boat and her unlucky crew! The lazy Magassa was only too glad to believe them, and returned home to his bananas and palm wine. Mtesa, however, knew the Bumbiré pirates too well to listen to such a tale, and he at once sent out a strong party to look for his friend "Stamlee."

Meantime, the Bumbiré natives had collected in force, with many friends from the mainland; and, when the men of Uganda sent a message of peace, they murdered the messenger. Then they sent an impudent message back, to say they were coming to kill all the strangers and eat up their goods.

Stanley dared not risk an attack on the water, for the natives might upset some of his heavy-laden canoes and sink his precious stores. Taking, therefore, only his armed men and Mtesa's warriors, he sailed to Bumbiré, and in a one-sided fight punished the pirates severely. Next day he was allowed to go on his way in peace; and on August 12 pitched a new camp at Dumo, in Uganda.

The message now came that Mtesa was at war with Uvuma, whose people had attacked Stanley a few months before. No one was ever allowed to leave the country when the king was at war, so Stanley left his caravan at Dumo, and went to look on at the fighting. On the way to Mtesa's army, at the Ripon Falls, poor "Jack," one of the bulldogs, was killed by a fierce native cow which had run wild. "Jack" tried to pin her; but, missing his grip, was crushed against a tree-trunk by her long, sharp horns. "Bull" and "Jack" were great friends, though sometimes they had quarrelled, but never seriously, about the first choice of bones or the best place to sleep. "Bull" now walked several times round the body of his companion, sniffing it well to make sure that he was dead; then he sat down on his haunches beside his friend, with his great, moist eyes staring blankly into space, as though trying to think out the great puzzles of his life.

Mtesa's army of 150,000 men and 325 canoes held a camp on the shore, looking over a narrow strait to an island on which the enemy had gathered. The Waganda, a word which means "people of Uganda," fought best on land; while the Wavuma, or "people of Uvuma," were much better sailors. Mtesa and Stanley sat on a hillside overlooking the straits, and watched great canoe fights every few days.

Between whiles the two men talked about many things, and especially of the religion of Christ; for Mtesa promised Stanley to become a Christian and have a mission station in his land.

One day an important chief of the Wavuma was taken prisoner, and Mtesa ordered him to be tied to a stake and burnt. Stanley, however, told the King that this was not loving his neighbour as himself; and Mtesa, after much persuasion, let the man go. Stanley was always being asked many questions of very different kinds. Once he was called upon to tell all the Waganda chiefs what an angel was like. Another time he was asked: "Stamlee, how is that the white men have long noses, while their dogs have very short noses; while almost all black men have short noses, but their dogs have very long noses?"

After many battles had been fought, Stanley helped Mtesa to make peace with the Wavuma, and he was then allowed to depart. Mtesa, who was very sorry to lose his friend, gave him many presents, amongst which were six walking-sticks and four white monkey skins. Stanley wanted to explore a lake called Muta Nzigé, now known as the Albert Edward Nyanza, and Mtesa sent one of his generals, Sambuzi, to escort him thither.

Stanley now broke up his camp at Dumo, and marched up the river Katonga till he met Sambuzi. Then on January 1, 1876, they crossed the border of Uganda; and, marching through the grand hill country of Ankolé, they at last came in sight of the Muta Nzigé. They encamped on a plateau overlooking the lake, with fifty feet of cliff between them and its shore, and there was no way down which the boat could be carried to the water. The natives were unfriendly, and at once sent a message to say they were coming to fight. Sambuzi and his men turned cowards and insisted on a retreat, and Stanley was obliged to go with them. On reaching the Katonga, Stanley left Sambuzi and set out for Ujiji, intending to explore the rest of Lake Tanganyika and Livingstone's river, the Lualaba.

There were no very great adventures on the way to Ujiji. Stanley spent a month in the Karagwé country, exploring the Kagera or Alexandra Nile, which is the largest, though not the longest, of the Nile sources. The people of Karagwé lived mainly on milk, and were strong, healthy, and gentle; for the tribes who eat the most meat are generally the most cruel and vicious. Their king, Rumanika, sent Stanley to the hot springs of Mtagata, where all the black invalids of the neighbouring countries went for the good of their health. There were six springs of different heat; and Stanley had the choice of many hot pools: while among the over-hanging trees baboons and long-tailed monkeys grinned, and gibbered, and chattered about the funny white creature who could take off his skin and put it on again after his bath.

On April 7, Stanley came to the top of a ridge overlooking the wide valley of the river Malagarazi. The rain-drops which fell behind him trickled towards the Nile on their way to the Mediterranean Sea; while those falling in front of him drained southward to Tanganyika.

While moving on through Usambiro, Stanley lost another of his best friends; for here his other bulldog did its last day's march, after tramping 1500 miles of African soil. The faithful "Bull" had a fine character. He never worried or fussed about anything; but he did everything in earnest. He seldom spoke; but, whenever he did, the men gripped their rifles, for they knew "Bull" never called "danger" for nothing. When there was trouble he was always on the spot, grimly and quietly doing his best; and he never seemed either very pleased or very disappointed with what he had done. In the fight at Vinyata he had been in the forefront of the battle, and no native dared face him. He grew worn out with the heat and toil of the journey, but he never showed it to any one, and the day he died he was trotting doggedly on in his usual place. Quite unexpectedly he sank on the ground and gave a look upward, as though to beg pardon for thus breaking down. Then, as if he meant his spirit ever to be in the vanguard, he fixed his big, wistful eyes down the forward track till the light faded from them in death.

While Stanley was resting at Serombo, the great warrior Mirambo, who now had made peace with the Arabs, came to pay a friendly visit to his brother, the chief of the town. The night before his arrival the big drums were beaten to make silence among the three thousand townsfolk in the streets. Then, with the jangling of iron bells, the pompous town-crier shouted the following: "Listen, O men of Serombo! Mirambo, the brother of Ndega, cometh in the morning! Be ye prepared therefore, for his young men are hungry! Send your women to dig potatoes, dig potatoes! Mirambo cometh! Dig potatoes, potatoes, potatoes, dig potatoes, to-morrow!"

Stanley made friends with Mirambo, and this saved him from a great deal of trouble with the natives on the way to Ujiji, where he arrived without mishap on May 27. Here he launched his boat, and made a voyage round the south end of Tanganyika, for he had already explored the northern end with Livingstone in 1871. He carefully examined the Lukuga creek, where Cameron in 1874 thought he saw an out-flowing river choked up with giant reeds. Stanley found out that there was no real river, but only a river-bed, down which the waters of Lake Tanganyika could run whenever they rose high enough to overflow.

Returning to Ujiji, Stanley now prepared to explore the Lualaba downwards from Nyangwé, the farthest point that Livingstone had reached. More than forty of his men now deserted him; but with the remainder, about 150 in number, he arrived at Nyangwé in safety on October 27. Near this place he met a famous Arab trader, Tippu Tib, who for Ł1000 promised to escort Stanley for sixty days' march with 400 followers. And thus Stanley made ready for the hardest journey he had yet known.