This event changed the course of Stanley's life. He looked upon Livingstone as the "Apostle of Africa" and the "daring pioneer" of its freedom; and now he pledged his life to carry on his old friend's work to the utmost of his power. Livingstone's heroic life and death turned all men's minds to African affairs; and in a short while Stanley was sent out by the Daily Telegraph  and the New York Herald.

In September 1874 he was again at Zanzibar, this time preparing to finish what Speke, Burton and Grant had begun at the head-waters of the Nile, and then to carry on Livingstone's work on the Lualaba. Three white men came with him: Frank and Edward Pocock, the sons of a Kentish fisherman, and a young clerk named Barker. He also brought a light and roomy boat called the Lady Alice, which could be carried in eight pieces and easily put together. Most of his old followers joined him, and Manwa Sera, one of Speke's faithful men, was made chief. Others came too; and each man had to promise before his relations that he would be a true and obedient servant to his master. Stanley also had to promise "on the word of a white man" that he would treat them kindly and with patience, and that he would not abandon them when sick.

Stanley left Bagamoyo on November 17 with about three hundred and fifty men and a few of their wives. He now tried Livingstone's plan of treating the unruly ones with patience and forbearance, but still he had much trouble with his men. The first night at Bagamoyo he had to lock up twenty of them for running riot in the town; and it took him three hours to soothe the angry townsfolk, who came with drawn swords to ask for justice. Before reaching Mpwapwa fifty deserters had got away, and on the plains of Uhumba, fifty more planned to desert, but were stopped by the punishment of their ringleaders. Stanley was really well rid of the worthless deserters; and his milder treatment made the others repay him a thousand-fold in the time of his greatest need.

The caravan took the old route as far as Mukondoku in Ugogo, and then struck northwards for Lake Victoria Nyanza. The part of Ugogo they crossed was mostly unfertile and much of it wilderness. At first water was sometimes scarce till the rainy season came on; then famine set in, for by that time of year the crops were almost all eaten. At Itumbe they were digging for water in the sandy bed of a dry stream, when they saw a storm on the hills. No rain fell near them; but in half-an-hour a river, forty yards wide and eighteen inches deep, came rushing down, only to dwindle away to nothing in a few hours. Once, too, at dead of night Stanley woke from his sleep to see his boots sail gracefully out of his tent on a flood; while his two bull-terriers, "Bull" and "Jack," were fighting for the biggest share of sitting room on an island made of an ammunition box.

Food grew scarcer and scarcer; and when they entered the wide and deserted jungle of Uveriveri and headed for Suna, they indeed learnt what hunger meant. There was no track; and for several days they crushed their way through thickets of brushwood, thorn-scrub and stunted trees, thrusting aside the stubborn branches that tore their skin and clothing. The guide lost his way, and Stanley had to steer by compass. When the useless native again found his landmarks, they were at the village of Uveriveri, nearly worn out and starving, and Suna was still twenty-eight miles off.

Four men and a donkey laden with coffee had lagged behind the caravan and were lost in the bush; and Manwa Sera, with twenty men, was at once sent to find them. Three of the stragglers were found dead from hunger and fatigue, but the fourth man and the donkey could not be found. There was no food to be had in the village; and Stanley, who could scarcely bear to see the gaunt bones and hollow eyes of the faces that looked to him for help, asked for volunteers to bring supplies from Suna. He now found out what men, made faithful by kindness and justice, will do for a leader they trust and respect. Forty of his followers, worn and weak as they were, started at once to get food for their sick and exhausted companions.

Next day, after a dismal and hungry night, Stanley and those who were still able to move ranged the neighbourhood in search of game, berries and roots, but without success. Some of the men, however, found the dead carcase of an elephant; and so cruel was their hunger, that they ate like wolves and were almost poisoned. Another night came, and still no food; but a happy thought made Stanley and Pocock look through the medical stores, and they found a quantity of fine meal for making gruel. Then there was joy on the famished faces of the men, who crowded round the camp fire, watching ten pounds of meal and twenty-five gallons of water, stirred round and round with a stick in a sheet-iron travelling-trunk. No watched pot ever seemed so long in boiling as this strange cauldron, but at last it seethed and bubbled, and then! It could not be called a meal; but for a while it stayed the dull and grinding pain at their waists, and gave them the strength to sleep.

Soon after nine o'clock that same night an eager ear heard a rifle shot in the far distance. It was the signal of the relief party; and in the early morning hours they came into camp, after tramping fifty-six miles in little more than a day and a half. They had only been able to bring enough millet to give the whole camp one meal. As soon as this was eaten, the plucky fellows insisted on starting at once, without further rest, so that the sick might reach Suna before nightfall.

From Suna they struggled on to Chiwyu where Edward Pocock died after a short illness. Famine still dogged their footsteps, and the caravan dragged its way into Vinyata like a file of spectres. Here they hoped to rest and recover, for food was more plentiful and the natives seemed friendly. Their Mganga, or "doctor of magic," brought an ox as a present, and was given four times its value in cloth and beads. Unluckily, some bales of wetted cloth had been spread out to dry; and Stanley saw his visitors give each other sly and suspicious looks.

Next day Stanley heard that two stragglers from the camp had been killed and a third badly wounded, and soon after a large body of armed natives gathered on a mound close at hand. Stanley at once told off sixty men under Pocock to take axes and build a stockade round the camp, while he himself went out with some of the riflemen to parley with the natives. Stanley did all he could to avoid bloodshed; for, as he afterwards said, he remembered how Livingstone had taught him forbearance. At first he succeeded, but afterwards another body of natives came up and forced on a quarrel. They were a set of robbers and murderers, and were bent on plundering the caravan. With savage war cries they rushed to the attack, but after an hour's sharp fighting they were driven back.

By nightfall the stockade was finished and loopholed all round, with "marksman's nests" at each corner; and the cover was cut and cleared away for 200 yards, so that no one could creep up to the camp without being seen. Stanley had only seventy rifles, none too much ammunition, and no food; so the caravan could not stand a siege for long. Distant war cries, too, told that men were gathering against them from far and near.

At daybreak the natives attacked in force; and, after driving them off, Stanley determined to make a sally, in order to get supplies for his hungry camp. He divided his seventy riflemen into seven companies of ten, each under a chief. Four companies were stretched out in open order into a wide fighting line; two more were held behind in reserve, and one was left to guard the camp; and thus the plucky band under their dashing leader went out against hundreds of natives.

All seemed going on well, when unluckily the company on the right flank grew rash, lost order, and were killed to a man. This disaster at once brought the second and third companies into straits, and soon they became hard pressed and lost heavily. Ruin now seemed certain; but Stanley, who was a practised soldier, kept a cool head. He rushed forward fifteen reserves under the gallant Manwa Sera; thus they not only saved the day, but swept the country for some miles towards the native stronghold, sacking and burning several villages. Stanley's men had lost twenty-one killed and three wounded; but they brought plenty of goats, oxen, and grain to the camp, and famine was at an end for a while.

On the following day the natives again attacked in greater numbers than ever. After driving them off Stanley saw that he must force his way out of the country before he was overwhelmed by still larger numbers. Keeping his men well together, he followed the natives, stormed their stronghold, and scattered them to the hills, while he recaptured some of his lost rifles. Then, before they had time to recover, he returned to the caravan and pushed onward by quick marches to the friendly and fertile Usukuma land.

They had three days' rest at Mombiti, where Stanley rewarded his brave men to such an extent that they named him "the man with the open hand." Near the headwaters of the river Simiyu, the longest of the Nile sources, they came into a land of plenty; and in two days they shot one giraffe, one buffalo, two gnu, and six zebra. The natives were kind and helpful, though at one place their curiosity became a nuisance. One inquisitive chief rudely forced his way into the tent where the strange white man was having an afternoon nap. A chorus of yells and snarls woke Stanley to see that "Bull" and "Jack" had pinned the chief by the wrists, and were trying to tug his arms out of joint. Stanley released him, and he showed better manners for the future.

Moving on, they passed through a country of rich downs covered with short green grass, where thousands of cattle, sheep, and goats crowded the pastures. At Abaddi they were able to buy an ox for eighteen pennyworth of cloth, and a goat for sixpence, while fowls were a shilling a dozen!

At last the caravan came over a ridge and saw Speke's mighty lake, the Victoria Nyanza, glistening like silver from the shore beneath them to the sky-line. With loud shouts of joy and songs of thanksgiving, they hurried down the hillside and camped near the beach at Kageyi. It was now February 27, 1875, and they had come 720 miles in 103 days.