The Victoria River was first explored by Europeans in 1839 when Captain J. C. Wickham arrived at its mouth in the HMS Beagle. He named the river after Queen Victoria. Such was the slowness of exploration of the Territory that it wasn't until sixteen years later that Sir Augustus Charles Gregory (after whom the local hotel is named) sailed from Moreton Bay to explore the estuary of the river. With a crew of eighteen and a number of scientists, Gregory sailed up the Victoria River and then explored Sturts Creek for 500 km before it disappeared into the desert. Gregory was eager to establish a town which, royalist that he was, he wanted to call Albert after Queen Victoria's husband. The plan came to nothing.
In 1879 Alexander Forrest crossed the Victoria River on his journey from the Western Australian coast to the Overland Telegraph Line. Four years later settlement occurred with the establishment of the huge cattle stations at Victoria Downs and Wave Hill. The stations, both of which lie hundreds of kilometres to the south of the present site, have important places in Territory history.
Victoria Downs, once Australia's largest pastoral property and the largest cattle station in the world, is synonymous with Sidney Kidman - the Cattle King. In the 1920s, after a malaria epidemic, John Flynn built a hospital on the station which was operated by the Australian Inland Mission until it closed down in 1942. Both the original homestead, which is located some kilometres south of the current Victoria Downs homestead, and the hospital are now listed as part of the National Estate.
Wave Hill, founded by the famous drover and stockman Nat Buchanan in 1883 and subsequently owned by the huge British firm Vesteys was the scene for the beginning of the Northern Territory land rights movement. In 1966 the Gurindji Aborigines who were working on the station, and being paid a pittance and living in sub-standard conditions, walked off the job and laid claim to the land. For years they pursued their claims and in 1975 Gough Whitlam's government handed over 3200 sq. km of land which had been taken back from Wave Hill. It was the first official recognition of the land rights claims of the Aborigines.
In his 1934 book Packhorse and Waterhole H.M. Barker explains how Wave Hill got its name when he writes: 'Greenhide Sam, struck by the sharp undulations of the plateau, suggested the name of Wave Hill.'