His Majesty's Armed Survey Vessel Lady Nelson was commissioned in 1799 to survey the coast of Australia. At the time large parts of the Australian coast were unmapped and Britain had claimed only part of the continent. The British Government were concerned that, in the event of settlers of another European power becoming established in Australia, any future conflict in Europe would lead to a widening of the conflict into the southern hemisphere to the detriment of the trade that Britain sought to develop. It was against this background that Lady Nelson was chosen to survey and establish sovereignty over strategic parts of the continent.

Lady Nelson left Portsmouth on 18 March 1800 and arrived at Sydney on 16 December 1800 after having been the first vessel to reach the east coast of Australia via Bass Strait. Prior to that date all vessels had sailed around the southern tip of Tasmania to reach their destination.

Lady Nelson's survey work commenced shortly after her arrival at Sydney, initially in the Bass Strait area. She was involved in the discovery of Port Phillip, on the coast of Victoria, in establishing settlements on the River Derwent and at Port Dalrymple in Tasmania, at Newcastle and Port Macquarie in New South Wales, and on Melville Island off the north coast of the continent.

At the end of the 1790s the New South Wales Colonial Government had no vessels capable of reaching the outside world. Supply (1793) was found to be unseaworthy in 1797 and was subsequently condemned. Reliance was also unseaworthy. Reliance was temporarily repaired to enable her to sail back to England, whither she departed in March 1800. The only other vessel under the control of the colonial government was Francis, a schooner of only 44 tons (bm). The situation was partially relieved when Buffalo arrived in May 1799, but the colony possessed no vessels for exploration and surveying.

In 1799 the Admiralty's Commissioners of Transport (the Transport Board), ordered a cutter of 60 tons (bm), to be built for their own use in the River Thames and called it Lady Nelson. Her design followed that of the armed cutter Trial, built in Plymouth in 1789 to a design developed by Captain (later Admiral) John Schanck [often spelled Schank]. Trial was unusual in that she had three sliding keels, or centre-boards, that the crew could raise or lower individually.

At the time there were several other vessels named Lady Nelson and this has led some authors to write that the vessel that is the subject of this article was employed on other duties before being sent to Australia.

Philip Gidley King, who was in England in 1799, was aware of the lack of vessels in New South Wales, and lobbied for Lady Nelson to be taken over for use in the Colony. The cost to the government was said to be £890. He personally inspected the vessel on 8 October 1799, whilst it was being fitted-out at Deptford, and suggested that:

as few seamen know anything about the management of a cutter, her being constructed into a brig would make her more manageable to the generality of seamen.