This paper discusses recognition from the legal and political perspective, particularly in relation to a referendum on amending Australia's constitution to recognize Aboriginal and Torres Strait Islander people. It reflects on the significant changes in thinking from the time when Europeans had arrived in Australia, declared the land “terra nullius” and the constitution was written based on this premise. Since 1901, only eight of 44 changes that were put to Australians via referendum have been successful. The difficulty faced by the “Recognize” campaign is discussed in this light, as well as the need for strong, bi-partisan political leadership and a groundswell of community support in order to deliver a positive outcome for a referendum.