The Victorian state government established the Archaeological and Aboriginal Relics Office under the Chief Secretary's Department, following the enactment of the Archaeological and Aboriginal Relics Preservation Act 1972. One of the original aims of the Relics office was to compile a list of archaeological sites throughout the State, which still continues as the Victorian Aboriginal Heritage Register. Initially staff consisted of the Protector of Relics (who was the Director of the then National Museum of Victoria and who did little direct archaeological work), the State Archaeologist, two Archaeologists, a Geologist, a Field Assistant and three Administrative staff.
In 1975 the Relics office was transferred to the newly established Ministry for Conservation and underwent a name change to the Victoria Archaeological Survey (VAS) Changes to the legislation did away with the postilion of "Protector" which had unfortunate connotations with the "Protector of Aborigines". In 1983 the VAS was again transferred to a new government department under the Ministry for Planning and Environment. Briefly, between April and May 1990 the Minister for Aboriginal Affairs had responsibility for state archaeological functions, but responsibility for these functions was then transferred to the Minister for Conservation and Environment. VAS also took responsibility for Maritime and historic archaeology which was tested through the results of a court determination that the definition of archaeological relics included historic relics.
Over 60 publications were prepared under the first director of the VAS Peter Coutts including many large scale surveys and excavation reports.
One of the innovations of the VAS, was the 'Summer Schools in Archaeology', which allowed students and members of the general public to participate in research-drive archaeological surveys and excavations. these were conducted from the mid-1970s to about 1980, and covered projects such as surveys and excavations of Aboriginal sites at Yambuk (1976-7), Kulki-Kulki near Swan Hill (1977), Keilor (1977-8), Hattah Kulkyn National Park, Nyah Forest, and Mallacoota, and excavations at the first settlement site at Corinella.
In February 1992 it was transferred back to the Minister for Aboriginal Affairs, and underwent another name change, to the Heritage Services Branch of Aboriginal Affairs Victoria. The Aboriginal, and maritime and historic functions were split in 1993 when maritime archaeology and historical archaeology became the responsibility of the department of Planning. This distinction was formalised in the Heritage Act 1995, which included provision for these archaeological places.