Transportation to the new protectorate was difficult and risky. It implied crossing deserts and arid regions packed with wild animals and hostile tribes. For IBEAC, keeping the route open had been a real torment, with strongly guarded forts along the way, each one requiring 2,000 fresh men every year. With the declaration of Uganda Protectorate and IBEAC's bankruptcy, the Uganda railway project was at last approved.

For the Bristish government, the strip of land from the coast to the Rift Valley was useless, but it ought to receive some sort of protection so as to administer and control the railway. Hence, the 1st of July 1895, the government declared the British East Africa Protectorate and assumed the direct management of both protectorates, taking the place of the wrecked IBEAC.

With a budget of three million two hundred and fifty thousand pounds and under the command of engineer George Whitehouse, in May 1896 started the construction of the railroad, which from the start was known as the Lunatic Express: the way should traverse 1,000 kilometers of inhospitable territory, along which it should climb 1,150 meters, cross the Equator, go down the Rift Valley and up again with 600-meter drops, apart from crossing a 160-kilometer swamp. The sleepers would be made of steel, since termites ate the timber.

For the construction, the English government brought from India 13,000 workers, coolies from lower castes, since the natives were considered by the racist colonial administration as perfect for porting but unsuited for construction. The works progressed quickly, at the expense of the lifes of many workers who died from malaria, dysentery, scurvy, cholera, ulcers and typhus. Tsetse flies decimated the pack animals and camps were always submitted to raids and attacks from the local tribes. Besides, the workers had to face a danger that became legendary: the man-eating lions of Tsavo.

Of all stories about lions that became fond of human flesh during the construction of the Lunatic Express, the most famous belong to J.H. Patterson. Colonel Patterson arrived in Mombasa in 1898 with the mission of building a bridge over river Tsavo. During the works, two big male lions, maneless as usual in the region, started to perform night raids into the camps to pull the workers out of their tents and devour them. The Indian men developed such a horror for the beasts that they nicknamed them the Ghost and the Darkness, which they believed to be possessed by evil local gods opposed to the railway. When finally Patterson managed to shoot down the two cats, these had eaten 28 Indian workers and an undefined number of local porters. The bridge was erected and still persists today, such a dull piece of engineering that, if it was not for the legend surrounding it, would pass totally unnoticed.

In 1899 the railway works reached a waterhole, one more of all those where Thomson had probably rested to refresh and water his beasts. It was a marshy pond in a place the Maasais knew as Nyrobi. Chief engineer George Whitehouse decided to establish there the main railway station to undertake the works at the Rift Valley. At the end of that same year, the place was already known as Nairobi, and the first adventurers and hunters began to settle there attracted by its good climate. At the same time, the colonial administration resolved to move from Machakos to the new city.

The 20th of December 1901, chief engineer Ronald Preston's wife laid the last rail in Port Florence, today Kisumu, at the shores of Lake Victoria. The last stretch from Kisumu to Kampala would follow later on. Thus ended the construction of one of the great engineering works in history, which still today is an essential artery in East African communications. In fact, the railway set the basis for building the country itself, since the main cities, save the coastal towns, were founded as stations for the Lunatic Express. The survivors among the Indian workers gave birth to one of the great communities of foreign origin that still persist in Kenya.

The railroad works also spilt much native blood, of those that reacted to the invasion of their lands: Giriamas, Taitas, Kambas, Kikuyus, Kisiis, Nandis and Elgeyos, all were brutally repressed for their skirmishes against the dominant power.

In 1902, the region of Uganda Protectorate west of Rift Valley was transferred to the British East Africa Protectorate, with the double purpose of setting the railway under one single administration and restoring the borderlines of Buganda kingdom. This nearly finished the definition of the boundaries of today's Kenya.