In 1861, forty-one year old Walker was appointed to lead Victoria's Burke Relief Expedition to the Gulf of Carpentaria. The party included seven Aboriginal troopers from the Native Mounted Police Force, most of whom had been with Walker on previous trips. They were armed with Terry rifles, double barrelled shot guns, and other weapons. The mounted party left Rockhampton on 7 September 1861 with around 50 horses. They followed the Barcoo and Thomson Rivers to the Norman River, which Walker named after Commander William Henry Norman. On the 26th November 1861 they found Burke's tracks and on 4th December they discovered the blazed trees that marked Burke's most northerly camp, Camp CXIX. From here Walker headed across the Gulf to meet Commander Norman and the HCMS Victoria. On the Stawell River, north-west of today's Hughenden the party encountered a number of Aboriginal people at a waterhole. The numbers of Aborigines increased to around 30 men while Walker's party had dinner. After dinner Walker's party mounted their horses and charged at the group:

'Now was shown the benefit of Terry's breech loaders, for such a continued steady fire was kept up by this small party that the enemy was never able to throw one of their formidable spears. Twelve men were killed and few, if any, escaped unwounded.'

At the Leichhardt River in the Gulf, a similar situation occurred, with heavy losses of Aboriginal life reported, and on returning to the Flinders River, two more Aborigines were shot at long range in order to show the strength of Walker's party.

E.B.W. of the World's News noted:

Before leaving the Gulf country Walker was forced into several skirmishes with the natives, in one of which, at least, they suffered severely, for the Native Police were never credited with an undue leaning towards mercy when the opportunity of showing their skill with the rifle presented itself in the shape of the fighting warriors of warrigal tribes.

On the 7 December Walker met Commander Norman at the Albert River. Storekeeper Flocheldt was ill and returned to Melbourne on the Victoria. He was replaced by Arthur Moore. Walker reported the finding of Burke's camp and resupplied, intending to follow Burke's tracks down to Eyre Creek and then to Adelaide. However Walker lost Burke's tracks in long grass and rocky outcrops and his limited supplies meant he decided to return to Rockhampton, where he heard of Howitt's discoveries at the Cooper.

Walker's blazed tree at Camp CXIX

Walker's Gulf Camp

Memorial at Hughenden