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

After loading 30 horses and forage, on the 24th August 1861 they left Brisbane to sail for the Gulf in company with the H.M.C.S. Victoria captained by Commander W. H. Norman.

A hurricane struck near Reine Island, and '...it was evident we were in great danger, but my officer and crew did their duty well and showed no fear; the explorers were however, completely upset, and bewailed their fate to such an extent that I really pitied them and endeavoured to keep up their .spirits as far as possible as I feared their terrors might affect the crew... ' was the Captains view of the situation.

Somewhat later the Firefly grounded adjacent to Sir Charles Hardy's Islands: '...Riot and drunkenness became the order of the day ... Sailors drank, Law and order set at defiance'...' says Landsborough's journal, '...Decks were covered with cases of spirits, wine, beer ... and the crew on the island very much the worse... for liquor ...' reported Captain Norman referring to the Firefly’s crew; '...the sailors of the Victoria ... broke into the hold of the Firefly and were drunk for days and ... plundered the ships stores...' responded Captain Kirby. It would never be resolved which crew was responsible for these actions.

The upshot of all of this was the ultimate salvage of the Firefly; all but one of the horses had been saved by the expedient of cutting a hole in the vessel's side and then leading and swimming them out The hulk was taken in tow by the Victoria after whatever repairs were possible, with the horses reinstalled. On Sunday 27th September both ships anchored in Investigator Road, adjacent to Sweers Island, where they found the Gratia and Native Lass, under charter to the Victorian Government, with stores and coal to bunker the Victoria. 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 landing the horses and supplies. This they did and all hands then faced the problem of manoeuvring the Firefly upstream to it. After three weeks they managed to coax the Firefly to the spot. Later she was moved to a channel close to the west bank where she could be pumped out and kept upright to serve as accommodation for some of the party.

The Firefly became the first ship to have entered the Albert River. When the expeditioners finally left, the Firefly was left to slowly rot and disappear under the murky waters of the Albert River.