Political map of Australia, New Zealand & the Southwest Pacific 06 June 1859 (Colony of Queensland): Although there had been a call for northeastern Australia to be separated from New South Wales (Colony of New South Wales) since the 1840s, debate raged over whether it should be a free or convict colony (Convicts in Australia) and where its southern border should lie. Eventually it was agreed that the new colony would be free, with Brisbane as its capital, and in 1859 the British Government established the Colony of Queensland (Separation of Queensland).