In September 1854 he received word that he had been appointed Governor of New South Wales, and when he left Hobart on 13 January 1855 he received a cheque for £2000 from the colonists to purchase a piece of plate as a memento of his sojourn among them.
After correspondence with the Secretary of State he was allowed to accept this.
One of his last official acts was to support the Legislative Council's request that the colony's name be changed to Tasmania.
In 1856, Denison became both Governor of New South Wales and "Governor-General in and over all our Colonies of New South Wales, Van Diemen's Land, Victoria, South Australia and Western Australia", a new title, which implied a role in encouraging co-operation between the colonies.
In response to the Crimean War, he strengthened Sydney's defences, strengthening the batteries on Dawes Point and building Fort Denison. He inaugurated the bicameral system of representative government in New South Wales and showed wisdom and tact in his dealings with the problems which arose, including the handing of executive power to the new Parliament.
He successfully opposed the Colonial Office's initial decision to put New England and the Clarence Valley in the new colony of Queensland.
In 1859, he appointed Queensland's first Legislative Council and began the process of electing a Legislative Assembly, inaugurated on 22 May 1860.
While he opened the colony's first railway in 1855, he ignored the problem of different rail gauges despite his role as Governor-General, although he was more active in developing arrangements for paying for postal connections with the United Kingdom, ameliorating inter-colonial tariffs and co-operation over the provision of lighthouses.