Vroege geschiedenis
Victoria was het toneel van veel vulkanische activiteit die 40 miljoen jaar geleden begon. De westelijke vulkanische vlakten, die 10% van de staat beslaan, zijn de op twee na grootste vulkanische vlakten ter wereld. De meeste van deze vlaktes werden ongeveer zes miljoen jaar geleden gevormd. Er zijn ongeveer 400 vulkanen op de vlaktes.
Het is onbekend wanneer de mens zich precies in Victoria vestigde. Op een plaats in de buurt van Keilor zijn bewijzen gevonden dat Australische Aboriginals meer dan 31.000 jaar geleden in de buurt van de Maribyrnong rivier woonden. Victoria was een van de dichtstbevolkte gebieden van Australië. De Aboriginals gebruikten vuurstokcultuur om de vulkanische vlakten regelmatig te verbranden, en deze werden enkele van de grootste grasvlakten ter wereld. Dit bracht grote aantallen dieren zoals kangoeroes en wallaby's in leven. De Kulin-federatie was een grote taalgroep die op de vlakten leefde en bestond uit de Watha wurrung, Boon wurrung, Woi wurrung, Daung wurrung en Djadja wurrung mensen. Andere groepen in Victoria waren de Jari Jari, Ladji Ladji, Wemba Wemba, Wergaia, Jardwadjali, Gunnai, Waywurru en de Taungurung. In de rivieren, kreken en wetlands hadden de Aboriginals grote visfuiken gebouwd om zowel vis als paling te vangen. In de wetlands van de Yarra River hadden sommige van deze vallen stenen muren van ongeveer 122 cm hoog.
Europese nederzetting
Eerste pogingen
Binnen tien jaar na de Britse vestiging in Sydney in 1788 begonnen ontdekkingsreizigers de kust van Victoria te onderzoeken. De eerste nederzetting in Victoria was in Sorrento, net voor de ingang van Port Phillip Bay. Een kleine groep van 51 soldaten, 308 veroordeelden, 17 vrije kolonisten, 12 ambtenaren, een missionaris en zijn vrouw, onder leiding van luitenant-gouverneur David Collins sloegen eind 1803 hun kamp op. Zij waren uit Engeland gekomen om een kolonie te stichten omdat de Britse regering bang was dat de Fransen zouden proberen het gebied op te eisen. Zij konden echter geen water vinden en gaven de nederzetting binnen zes weken op. Zij gingen verder naar het zuiden en begonnen met de vestiging van Hobart, Tasmanië. In Sorrento ontsnapte een veroordeelde, William Buckley. Hij leefde met Aboriginal stammen totdat hij de Europeanen weer ontmoette toen Melbourne werd gevestigd in 1835. Op 12 december 1826 probeerden kapitein Samuel Wright, luitenant Burchill, ontdekkingsreiziger William Hovell en 21 veroordeelden een nederzetting te stichten bij Corinella, aan Westernport Bay. Ook dit was geen succes en de groep keerde op 19 februari 1828 terug naar Sydney.
Hoewel de twee officiële pogingen om zich in Victoria te vestigen waren mislukt, waren er een aantal onofficiële nederzettingen langs de kust. Vanaf 1820 woonden kleine groepen mensen op verschillende plaatsen langs de zuidkust, waaronder Phillip Island. Zij jaagden op zeehonden en walvissen. De Launceston Fishing Company had een basis in Portland Bay. Deze jagers raakten vaak in conflict met de Aboriginal gemeenschappen. De Europeanen maakten vaak Aboriginal vrouwen buit om te gebruiken als slaven en voor seks. Edward Henty verhuisde naar Portland Bay en begon in december 1834 met de schapenhouderij. Deze nederzettingen waren in strijd met de wet, want de Britse regering probeerde de gebieden waar zich nederzettingen bevonden te beperken. Zij voerden aan dat zij niet in staat waren steun te verlenen aan afgelegen en geïsoleerde nederzettingen. Herhaalde verzoeken om officiële toestemming om zich in Victoria te vestigen werden door de regering afgewezen.
John Batman
In 1835 vormde een groep kolonisten, boeren en regeringsambtenaren uit Tasmanië de Port Phillip Association. Onder leiding van John Batman, die van William Hovell had gehoord over de grasvlakten, besloot de groep de Britse regering te negeren en kudden schapen naar Victoria te verplaatsen. Batman landde op 29 mei 1835 bij Indented Head in Victoria. Hij begon met de verkenning van Port Phillip Bay. Op 6 juni 1835 ontmoette hij Aboriginal leiders in de buurt van Merri Creek, en sloot een verdrag. In dit verdrag stemden de Aboriginals ermee in dat Batman hun land mocht gebruiken voor zijn schapen. In ruil daarvoor mochten ze op het land blijven, zouden ze voedsel en goederen krijgen, en zouden ze bescherming krijgen tegen andere Europeanen. Dit was het enige verdrag dat ooit met de Australische Aboriginals werd gesloten. Op 26 augustus 1835 verklaarde de gouverneur van New South Wales, Sir Richard Bourke, dat het verdrag in strijd was met de wet. Het land behoorde toe aan de kroon, en niet aan de Aboriginals.
Eind 1835 wijzigde de Britse regering haar beleid ten aanzien van de vestiging in Oost-Australië. Mensen kregen toestemming om grote delen van het land te gebruiken voor schapenteelt. Als mensen een vergoeding van 10 pond betaalden, mochten ze zich vestigen waar ze maar wilden. Deze boeren werden bekend als "krakers", omdat zij op het land "zaten", waarvan zij geen eigenaar waren. Het effect van dit nieuwe beleid was dat er zich tussen 1835 en 1838 meer land vestigde dan sinds 1788 het geval was geweest. Het is beschreven als de snelste landbezetting in de geschiedenis. Tegen 1849 hadden slechts 1019 krakers 17,7 miljoen hectare land in bezit genomen.
Het effect van de snelle landbezetting had verschrikkelijke gevolgen voor de Victoriaanse Aboriginals. De krakers verplaatsten hun schapen naar de graslanden die ooit de voornaamste voedselbron van de Aboriginals waren geweest. De krakers bouwden hun boerderijen in de buurt van de waterpoelen en kreken waar de Aboriginals duizenden jaren lang hun kamp hadden opgeslagen. De Aboriginals begonnen schapen te doden om op te eten, en probeerden de mensen ervan te weerhouden hun land in te pikken. De vroege kolonisten probeerden de Aboriginals van het land te verwijderen. Soms werden ze verjaagd, en soms werden ze vermoord. In Murdering Creek, bij Camperdown, bijvoorbeeld, werden 35-40 mannen, vrouwen en kinderen doodgeschoten door de manager van Glenorminston Station, Frederick Taylor en enkele van zijn landarbeiders.
Goud
Op 28 juni 1851 werd in Victoria goud gevonden in Clunes. Met verdere vondsten in Ballarat, Bendigo en Castlemaine nam de bevolking enorm toe doordat mensen van over de hele wereld kwamen.
