Gregory reviewed the problem from a logical standpoint. He decided to follow the northern limit of the desert to the westward, until he should find a southern-flowing watercourse which would afford him the opportunity to make a dash beyond its confines.
On the 15th of February he came to a small flat which gradually developed into a channel and ultimately became a creek, running first west, and then south-west. This gave him his desired opening, and he pursued the course of the creek through good open country, finding the water plentiful, though shallow. On February 20th, however, the channel of the creek was lost in an immense grassy plain. The country to the south being sandy and unpromising, Gregory kept westwards, and succeeded in again picking up the channel, now finding the water in it to be slightly brackish. That day he crossed the boundary of Western Australia. The creek now gave promise of continuity, the water-holes taking on a more permanent appearance. It was now pursuing a general south-west course, and Gregory, though still rightly anticipating that it would eventually be lost in the dry interior, determined to follow it as far south as should be compatible with safety. He named the creek Sturt's Creek, after the gallant explorer of that name, who was naturally then often in his mind. The creek maintained its southern course, until, on the 8th of March, it ran out into a mud plain and a salt lake.
"Thus, after having followed Sturt's Creek for nearly 300 miles, we have been disappointed in our hope that it would lead to some important outlet to the waters of the Australian interior; it has, however, enabled us to penetrate far into the level tract of country which may be termed the Great Australian Desert."
Gregory, convinced that no useful results could arise from any attempt to penetrate the inhospitable region to the south, determined to return before the rapidly-evaporating water on which they were dependent should vanish and cut off all retreat. He therefore retraced his steps up Sturt's Creek, and on the 28th of March arrived at his temporary depot, where he found the men all well and the horses much improved in condition.
On the 2nd of April, A.C. Gregory, taking his brother Henry, Baines, and one man, started on an excursion to examine the eastern tributaries of the Victoria, and was absent a little over a fortnight. On their return, the whole of the members started for the landing-place on the Victoria, which they reached on the 9th of May. After all arrangements and preparations had been completed, Gregory, with most of the party, started on the return journey overland to Moreton Bay. The Tom Tough, now caulked and repaired, was to make her way to the Albert River in the Gulf of Carpentaria, where they would again probably meet.
Traversing the tributaries of the Victoria on his homeward way, Gregory met with no remarkable incident until his arrival on the Elsey, a tributary of the Roper River, which he named after the surgeon of the expedition. It was here that he came upon the last authentic trace of Leichhardt. He describes his discovery as follows:--
"There was also the remains of a hut and the ashes of a large fire, indicating that there had been a party camped there for several weeks; several trees from six to eight inches in diameter had been cut down with iron axes in fair condition, and the hut built by cutting notches in standing trees and resting a large pole therein for a ridge; this hut had been burnt apparently by the subsequent bush fires, and only some pieces of the thickest timber remained unconsumed. Search was made for marked trees, but none found, nor were there any fragments of leather, iron, or other equipment of an exploring party, or of any bones of animals other than those common to Australia. Had an exploring party been destroyed here, there would most likely have been some indications, and it may therefore be inferred that the party proceeded on its journey. It could not have been a camp of Leichhardt's in 1845, as it is 100 miles south of his route to Port Essington; and it was only six or seven years old, judging by the growth of the trees; having subsequently seen some of Leichhardt's camps on the Burdekin, Mackenzie and Barcoo Rivers, a great similarity was observed in regard to the manner of building the hut and its relative position with regard to the fire and water supply, and the position in regard to the great features of the country was exactly where a party going westward would first receive a check from the waterless tableland between the Roper and Victoria Rivers, and would probably camp and reconnoitre ahead before attempting to cross to the north-west coast."
From the Roper the party travelled around the shore of the Gulf, keeping rather more inland than Leichhardt had done. On reaching the Albert they found that the Tom Tough had not yet arrived at the rendezvous; and Gregory, leaving a marked tree with a message indicating the situation of some instructions he had buried, pushed onwards.
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.