Finding it boring, he quit after a few weeks, and set sail for Australia with his friend Lord Percy Douglas.

Late in 1893, Douglas was appointed a director of a new mining exploration company, thus securing finances for Carnegie's prospecting.

In March 1894, Carnegie commenced his first prospecting expedition, in the company of a prospector and camel handler named Gus Luck.

The party initially travelled north, but hearing rumours of promising country near Lake Roe, they turned to the south east.

Early in February, after failing to locate a pool at Erlistoun, the party sought water in a granite outcrop near Lake Darlot, about 60 km (37 mi) east of the present-day town of Leinster.

Finding that his family were disappointed and embarrassed by his lack of an education and career, he returned to Australia determined "to prove that I am not the useless devil they have prophesied I would become".

Carnegie invested his profits from the two mines in preparations for his major expedition; he proposed to travel almost 1,600 km (990 mi) from Coolgardie to Halls Creek.

Much of the area through which he intended to travel was unexplored and unmapped, and Carnegie hoped to find good pastoral or gold-bearing land, and to make a name for himself as an explorer.

What heartbreaking country, monotonous, lifeless, without interest, without excitement save when the stern necessity of finding water forced us to seek out the natives in their primitive camps.

However, on 2 November, with their journey nearing completion, a number of Carnegie's camels ate poisonous plants, and three died.

Four weeks later, with the party only eight miles (13 km) from the Derby–Halls Creek road, Stansmore slipped while crossing a ridge, and dropped his gun.

On arriving at Halls Creek, the party were informed that two members of the Calvert Exploring Expedition were missing in the desert.

Carnegie's expedition was originally intended to terminate at Halls Creek, but since they had found no gold-bearing or pastoral land, the party decided to continue exploring, by returning to Coolgardie by a more easterly overland route.

The party left Halls Creek on 22 March 1897, heading east then southeast, before eventually turning south.

However he was keen to resume exploring, and he expressed interest in joining an expedition from Cape Town to Cairo before eventually deciding against it.