His route from the Albert lay along much the same line of country as that followed by Leichhardt during his journey to Port Essington.  He did not, however, make such a wide sweep to the north, up to the Mitchell, but struck away from Carpentaria at the Gilbert River.  He corrected the error Leichhardt had fallen into over the situation of the Albert, and re-named the river that he had mistaken the Leichhardt.  The exploring party reached the settled districts at Hay’s station, Rannes, south of the Fitzroy; and thence reached Brisbane on the 16th of December, 1856.

To advance the search after Leichhardt, the interest in whose fate had been stimulated by the discovery made by Gregory, a public meeting was held in September, 1857, at which resolutions were passed requesting monetary assistance from the Government, and offering the leadership of a new expedition to A.C.  Gregory.  The appeal was successful, and accordingly in March, 1858, Gregory left Euroomba station on the Dawson with a party of nine in all, one of his brothers going as second.  The expedition was equipped for light travelling, taking as means of carriage pack-horses only, of which there were thirty-one, as well as nine saddle-horses.

Gregory crossed the Nive on to the Barcoo, which he proceeded to run down, finding the country in a very different condition from that in which it bloomed when Mitchell rode rejoicingly along what he thought was a Gulf river.  A sharp look out was of course kept for any trace of the missing party, and on the 21st of April they came across another marked tree.

“We discovered a Moreton Bay ash (Eucalyptus sp.), about two feet in diameter marked with the letter L on the east side, cut through the bark about four feet from the ground, and near it the stumps of some small trees that had been cut with a sharp axe, also a deep notch cut in the side of a sloping tree, apparently to support the ridge-pole of a tent, or some similar purpose; all indicating that a camp had been established here by Leichhardt’s party...No other indications having been found, we continued the search down the river, examining every likely spot for marked trees, but without success.”

Approaching the Thomson River, they found the country suffering from drought although the river was running in consequence of some late rains.  As winter was now approaching, there was however no spring in the vegetation, and their horses were suffering great hardship.  On the 15th of May they found themselves beyond the rainfall, and realised that lack of water was likely to be added to an absence of grass.