L'histoire du Victoria aborde l'État australien du Victoria à partir de l'arrivée des Européens. Les Aborigènes ne connaissant pas l'écriture, leur occupation du pays rentre dans la préhistoire du Victoria (voir l'article Préhistoire de l'Australie).
Époque pré-européenne
La première présence humaine sur le continent australienne remonte de à – suivant les différents chercheurs – avant notre ère. À cette époque, huit détroits séparaient Java et l'Australie. L'Australie – y compris la Tasmanie – et la Nouvelle-Guinée étaient fusionnées. Les premières personnes durent donc arriver en bateau au nord d'Australie, découvrant un horizon inconnu. Les colons se sont ensuite déplacés progressivement vers le sud et, par la suite, sont arrivés en Victoria. Il y a environ , à la fin de la période glaciaire, la Nouvelle-Guinée et la Tasmanie se sont séparées du reste du continent et les Aborigènes ont commencé une longue période d'isolement coupée de toute influence extérieureGeoffrey Blainey; A Very Short History of the World; Penguin Books; 2004; .
La région comprenant Port Phillip et la vallée du fleuve Yarra, où est située aujourd'hui Melbourne, était la patrie de la nation Kulin, une communauté de plusieurs groupes linguistiques d'Aborigènes australiens, dont les ancêtres avaient vécu dans la zone depuis plus de Gary Presland, The First Residents of Melbourne's Western Region, (édition revue), Harriland Press, 1997. . Presland dit en page 1 : « Il y a des preuves montrant que des hommes vivaient il y a environ dans la vallée de la rivière Maribyrnong, près de Keilor, l'actuelle banlieue de Melbourne. ». Les Kulin vivaient aisément de la pêche, de la chasse et de la cueillette, Port Phillip et ses prairies environnantes offrant des ressources alimentaires abondantesGary Presland, Aboriginal Melbourne: The Lost Land of the Kulin People, Harriland Press (1985), seconde édition 1994, . Ce livre décrit en détail les témoignages archéologiques concernant la vie, la culture, la collecte de nourriture et la gestion foncière des aborigènes, particulièrement pendant la période comprise entre la formation du détroit de Bass et de Port Phillip, il y a 7 à , et la colonisation européenne au ..
Beaucoup des Aborigènes qui vivent maintenant à Melbourne descendent de nations aborigènes originaires d'autres parties du Victoria, mais il y a toujours des personnes qui s'identifient comme des Wurundjeri ou des Boon warung, descendants des nations originaires de la région de Melbourne. Alors qu'il y a peu de signes manifestes de la présence aborigène dans la région de Melbourne, il y a une abondance de lieux à signification culturelle ou religieuseMeyer Eidelson, The Melbourne Dreaming. A Guide to the Aboriginal Places of Melbourne, , Aboriginal Studies Press, Canberra, 1997. Reprint 2000. Voir aussi Meyer Eidelson, The Footballer, First in the league, in Walks in Port Phillip. A guide to the cultural landscapes of a City, consulté le novembre 2008.
Le temps du rêve aussi appelé le rêve, est le thème central de la culture des Aborigènes d'Australie. Il explique les origines de leur monde, de l’Australie et de ses habitants. Selon leur tradition, des créatures géantes, comme le Serpent arc-en-ciel, sont sorties de la terre, de la mer ou du ciel et ont créé la vie et les paysages australiens. Leurs corps géants ont créé des fleuves et des chaînes de montagnes mais leur esprit est resté dans la terre, rendant la terre elle-même sacrée aux peuples indigènesThe First Australians: they Have Come to Stay par SBS TV, 2008.. Les arts visuels ont une longue histoire en Victoria avec les peintures sur paroi et les peintures sur bois aborigènes. Les dessins et figures qu'ils peignent ont tous une signification bien particulière liée à la mythologie du rêve .
La découverte par les Européens
Chargé par le gouvernement britannique de vérifier l'existence d'un territoire appelé Terre australe et venant de Nouvelle-Zélande en 1770, le capitaine James Cook sur l'Endeavour aperçut le 20 avril 1770 les premières terres du futur Victoria en un point qu'il nomma point Hicks, environ à l'ouest de l'île de Gabo avant, en raison des courants et condition météorologiques, de retourner vers l'est puis le nord pour longer la côte est de l'Australie.
Par la suite, les navires venant du Royaume-Uni pour aller à Sydney en passant par Le Cap et le sud de l'Australie contournaient la Terre de Van Diemen, la future Tasmanie, par le sud avant de remonter vers le nord jusqu'à leur destination. Plusieurs capitaines avaient noté l'étendue d'eau séparant la Tasmanie de la côte Est de la Nouvelle-Galles du Sud et se demandaient si c'était une grande baie ou un détroit. Les survivants du Sydney Cove, un bateau échoué dans l'archipel Furneaux pensaient qu'il pourrait s'agir d'un détroit.
Pour régler la question, le gouverneur George Hunter envoya George Bass explorer la région dans une baleinière. Après avoir atteint la péninsule Wilsons et Western Port en janvier 1798, Bass fut obligé par le mauvais temps et le manque de moyens de revenir à Sydney. Il revint sur les lieux avec Matthew Flinders en décembre 1798 et traversa le détroit, apportant la preuve de son existence.
En décembre 1800, le lieutenant James Grant sur le Lady Nelson, reliant Le Cap à Sydney, traversa le détroit de Bass d'ouest en est. Le gouverneur King, déçu par l'imprécision de la traversée, le renvoya enquêter de façon plus approfondie sur le détroit. Le mauvais temps l'empêcha d'aller au-delà de Western Port, où il resta pendant cinq semaines, semant du blé, plantant des arbres fruitiers et des légumes sur Churchill Island au large de Phillip Island.
En janvier 1802, le lieutenant John Murray sur le Lady Nelson visita Western Port et entra dans la baie de Port Phillip, le 14 février. Il nomma Arthur's Seat une colline, explora la baie de Corio et prit officiellement possession de la baie (qu'il nomma Port King) pour la Grande-Bretagne.
Trois semaines plus tard, l'explorateur français Nicolas Baudin traversa le détroit d'est en ouest et fut le premier à le cartographier sérieusement dans sa partie ouest.
Le 26 avril 1802, Flinders, ignorant la précédente visite de Murray, pénétra dans la baie de Port Phillip pour explorer la région, escalada l'Arthur's Seat, traversa Mornington et la péninsule Bellarine et grimpa sur les You Yangs.
En janvier 1803, le lieutenant Charles Robbins sur la goélette Cumberland fit le tour de la baie de Port Phillip. Il avait avec lui l'arpenteur-général Charles Grimes et le botaniste James Flemming. Au fond de la baie, ils trouvèrent un cours d'eau et le remontèrent jusqu'à sa bifurcation très rapide. Ils remontèrent la branche ouest et la nommèrent rivière salée (l'actuelle Maribyrnong) jusqu'à ce qui est maintenant Braybrook, puis la branche est à l'eau douce (l'actuel Yarra) jusqu'à Dights Falls. Ils eurent une réunion amicale avec les peuples autochtones et regagnèrent leur navire par la baie de Corio. Ils conclurent que le meilleur site pour un point de peuplement serait sur le bord de la rivière d'eau douce au nord du fond de la baie, mais ils étaient peu enthousiastes sur le sol et son potentiel agricole.
La colonisation britannique
Quand la Grande-Bretagne eut à affronter la France au cours des guerres napoléoniennes, le gouverneur King remarqua que le détroit de Bass pouvait, en temps de guerre, servir à abriter des troupes ennemies, et, en temps de paix, servir d'importante route commerciale. L'apparition concomitante des navires du Français Nicolas Baudin dans la région le renforça dans l'idée que la France était intéressée par le site. En outre, il était à la recherche d'une autre zone pour implanter des colonies pénitentiaires afin de diminuer le nombre de condamnés à Sydney et réduire la pression sur les ressources alimentaires. Port Phillip, avec un climat favorable, d'importantes ressources de pêche et de chasse, semblait un lieu idéal pour un autre point de colonisation.
Une description complète des découvertes de Murray et de Flinders, avec les explications de King, mais sans le rapport de Grimes, arriva en Angleterre alors que le Calcutta s'apprêtait à partir pour Sydney avec son chargement de condamnés. En février 1803, Lord Hobart, le secrétaire d'État aux Colonies changea la destination du navire pour Port Phillip. Le 24 avril 1803, le Calcutta, commandé par le lieutenant-colonel David Collins quitta l'Angleterre accompagné par un navire chargé de matériel l'Océan. À bord se trouvaient quelque 300 détenus de sexe masculin, quelques hommes libres, une douzaine de fonctionnaires civils, une garde d'environ 50 marins, les épouses de 36 hommes, plus 38 enfants.
Le groupe arriva à Port Phillip, le 9 octobre 1803 et choisit de s'installer sur le site de Sullivan Bay près de l'actuelle ville de Sorrento.
Collins fut rapidement déçu par la région. Les rapports des équipes chargées d'explorer la région, dirigées par le lieutenant James Tuckey et le géomètre George Harris, décrivirent les courants forts, les sols sablonneux, les bois rares, les zones marécageuses et le manque d'eau douce. Les Anglais durent également affronter les aborigènes Wathaurungs près de la baie de Corio, tuant leur chef - le premier autochtone tué par les Européens au Victoria.
Collins fit part de ses critiques au gouverneur King, qui l'approuva et recommanda le déplacement de la colonie. Le 18 décembre, il partit sur le Calcutta pour l'Angleterre et on commença à organiser l'évacuation. Ce fut fait en deux voyages de l'Océan en janvier et mai 1804, aidé par le Lady Nelson qui se trouvait à proximité, chargé de cartographier la région de Port Dalrymple, l'actuelle George Town sur la côte nord de la Tasmanie. Les déportés furent transférés vers la nouvelle colonie de Hobart, fondé par le lieutenant John Bowen au centre pénitentiaire de Risdon Cove, en septembre 1803.
La brève colonisation de Sorrento tourna court et laissa seulement quelques vestiges pour les touristes. On reprocha par la suite à Collins de ne pas avoir étudié la baie de manière approfondie, en particulier le nord de la baie avec sa rivière d'eau douce et d'avoir été trop vite dans sa condamnation de la baie. Le site de la première colonie est maintenant une réserve incorporant certaines tombes de l'époque.
Quand Collins quitta la région, il y laissa un homme, un condamné, William Buckley, qui avait réussi à s'échapper et était présumé tué par les Aborigènes. Il devait revoir un nouvel européen seulement en 1835.
Pendant les trente années suivantes, quelques chasseurs de phoques et baleiniers firent escale sur la côte sud de la Nouvelle-Galles du Sud. En 1826 l'explorateur français Jules Dumont d'Urville visita un de ces camps sur Phillip Island. Il y eut pendant un court laps de temps (de novembre 1826 à avril 1828) l'implantation d'une nouvelle colonie pénitentiaire à Corinella à Western Port sous le commandement de Samuel Wright, afin de protéger les abords de la baie. Un chasseur de phoque, William Dutton, construisit une cabane sur les rives de la baie de Portland en 1829.
L'intérêt grandit pour la côte nord du détroit de Bass thumb|Hamilton Hume, en 1824-1825, avec William Hovell, il découvrit la route entre Sydney et la baie de Port Phillip, dans laquelle se trouve Melbourne.