After a voyage to Norfolk Island, Murray was instructed to continue the exploration of the southern Australian coastline.

He set out from Sydney on 12 November for the Kent Group, where he successfully navigated and charted the passage between Deal and Erith Islands, which would later be named in his honor.

On 4 January 1802, he sighted the entrance to Port Phillip, but decided it was too dangerous to navigate, so continued to survey the east coast of King Island.

During the chase, Murray watched with a spyglass and fired the ships' carronades loaded with roundshot and grapeshot at the Aboriginal people to panic them, though he says this was almost certain to have done no damage.

Murray wrote after the incident: "Thus did this treachery and unprovoked attack meet with its just punishment and at the same time taught us a useful lesson to be more cautious in future.

With respect to the size of these natives they are much the same as at Sydney, their understanding better though, for they easily made out our signs when it answered their purposes or inclination.

I conclude they live entirely inland, and if we may judge from the number of their fires and other marks this part of the country is not thin of inhabitants.

On 22 July 1802, Murray set off again in the Lady Nelson, which had become a supply ship accompanying HMS Investigator, commanded by Matthew Flinders, in the circumnavigation of Australia.

Due to her old sails and a need for caulking, she proved unfit and on 17 October, when they were off the Cumberland Islands, Flinders ordered Murray to return to Sydney.

He appears as the surveyor of several English coastal charts between 1804 and 1810,[4] which suggests he succeeded in repairing his reputation with the Admiralty, on behalf of which the maps were made.

There is record of a small vessel, The Herring, being lost in November 1814 under the command of a Lieutenant John Murray, though it is not certain if he was the same person because the name is relatively common.

One source states that Murray later attained the rank of captain, and subsequently lost his life with a ship under his command outside Port Phillip Heads,[5] but the origin of that claim is unknown.