As it was considered that Burke would have attempted to make a straight course from Eyres Creek to the Albert, the latter was selected as a starting point. The 250 ton brig Firefly captained by T. Kirby was chartered to carry Landsborough, his party and their supplies to last for six months, before proceeding on to Surabaya. She sailed from Melbourne on 29th July 1861. It was to be an eventful journey.

After loading 30 horses and forage they left Brisbane with the H.M.C.S. Victoria, captained by Norman. On the 24th August, a hurricane struck near Reine Island. Later the Firefly grounded adjacent to Sir Charles Hardy's Islands: 'Riot and drunkenness became the order of the day...' both Captains later claiming the other's crew as being responsible for these actions.

The Firefly was taken into tow by the Victoria and whatever repairs made that were possible. On Sunday 27th September both ships anchored in Investigator Road, adjacent to Sweers Island. A camp was established on the island as a land base.

Lieutenant Woods and Landsborough went to find a channel into the Albert suitable for unloading. After three weeks they managed to coax the Firefly to the spot, and she became the first ship to have entered the Albert River.

Landsborough with two other white and two black expeditioners left on 16th November with supplies for 90 days.

On Tuesday 19th November 1861 Landsborough's group '... camped beside a river full of fine clear running water, shaded by drooping tea trees, swamp oaks etc. ...' As it was unnamed on the charts he gave it the name of the Gregory River and remarked that it was '... the finest and greenest looking river I have seen in Australia... " To the south of the Gregory he named the O'Shanassy and the Prior Ranges - the site of Riversleigh - the Herbert River (now the Georgina) and from here moving onto the Barkly Tableland which he also named. Landsborough's reconnaissance of the Gregory revealed a great extent of fine pastoral country.

Landsborough returned to base camp at the Albert on the 19th January l862, where after a confrontation with Captain Norman of the Victoria he decided to return south by land. Accompanying him were three Aborigines plus Bourne and Leeson.

The necessary and scarce provisions were issued and Landsborough's depleted group left the camp on the Albert, also leaving the sadly crippled Firefly to rot where she lay with a sealed tank of supplies buried near a tree on which the word 'DIG' was inscribed.

They made for the Flinders by way of the Leichhardt and arrived at that river on 19th February. Going on he discovered and named the hills Fort Bowen and Mounts Brown and Little. Further on he named Walkers Creek before arriving back in familiar territory to discover the fate of Burke and Wills. The party proceeded to Darling, then finally to Melbourne.

In 1866 Landsborough returned to Burketown which had been established close to his camp on the Albert, to become police magistrate of the Burke district. A few weeks after his arrival there, he evacuated the population to Sweers Island due to Gulf Fever.