L'histoire de Melbourne détaille le développement de cette cité depuis le début de la colonisation jusqu'à son épanouissement en un centre commercial et financier moderne, seconde plus grande cité de l'Australie.
Époque pré-européenne thumb|200px|Aborigènes sur le ruisseau Merri par Charles Troedel. 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, , , Aboriginal Studies Press, Canberra, 1997. Reprint 2000. Voir aussi Meyer Eidelson, , in Walks in Port Phillip. , consulté le novembre 2008.
Exploration européenne et fondation de Melbourne thumb|L' Enterprize, la goélette de John Pascoe Fawkner atterrissant à Melbourne. thumb|right|Impression d'artiste sur la signature du traité de Batman dans les années 1880. thumb|Collins Street, Melbourne, en 1839. Aquarelle de W. Knight. thumb|Débarquement à Melbourne en 1840, aquarelle de W. Liardet (1840). En 1797, alors qu'il faisait route vers l'ouest pour atteindre la baie de Western Port, George Bass fut le premier Européen à traverser ce qui allait s'appeler le détroit de Bass, qui sépare le continent australien de la Tasmanie. En 1802, l'explorateur australien John Murray, à bord du brick Lady Nelson, entra dans la baie de Port Phillip, suivi peu de temps après par Matthew Flinders. En 1803, Charles Grimes trouva l'embouchure du fleuve Yarra, et marcha jusqu'à Keilor. Un peu plus tard en 1803, le gouverneur britannique de Nouvelle-Galles du Sud, Philip Gidley King, qui craignait l'occupation par les Français de la zone du détroit de Bass, envoya le colonel David Collins avec un détachement de 300 bagnards établir une colonie à Port Phillip. Collins arriva sur le site de Sorrento, sur la péninsule de Mornington, en , mais le manque d'eau douce l'obligea à renoncer. En , il transféra la colonie en Tasmanie, et devint ainsi le fondateur de la ville d'Hobart. Parmi les forçats de Sorrento, il y avait un garçon nommé John Pascoe Fawkner, qui allait revenir coloniser la région de Melbourne.
Les côtes nord du détroit de Bass furent ensuite abandonnées pendant vingt années aux chasseurs de baleines et de phoques. En 1824, Hamilton Hume et William Hovell, voyageant par voie de terre depuis la Nouvelle-Galles du Sud, ne réussirent pas à trouver Western Port, leur destination, mais atteignirent à la place la baie de Corio, où ils trouvèrent de bons pâturages. Mais il fallut dix années supplémentaires pour qu'Edward Henty, un éleveur de Tasmanie, établît en 1834 un élevage de moutons illicite sur des terres de la Couronne, dans ce qui est maintenant l'ouest du Victoria.
John Batman, un fermier qui avait réussi dans le nord de la Tasmanie, désirait aussi davantage de pâturage. En , il traversa le détroit, se rendit à Port Phillip jusqu'à l'embouchure du Yarra. Il explora une vaste zone, où se trouvent maintenant les banlieues nord de Melbourne. Le , en tant que membre d'un groupement d'hommes d'affaires, connu sous le nom de Port Phillip Association, il signa avec les Aborigènes locaux le traité de Batman, dans lequel il se proposait d'acheter de terre autour de Melbourne et 400 autres km autour de Geelong, près de la baie de Corio au sud-ouest. Le , il écrivit dans son journal : « Ainsi le navire a remonté la grande rivière... et... je suis heureux de déclarer qu'à environ dix kilomètres, j'ai trouvé de la bonne eau et très profonde. Ce sera l'emplacement d'un village ». Cette dernière phrase devint plus tard célèbre, considérée comme la déclaration de la fondation de Melbourne.
Batman retourna à Launceston et commença à échafauder des plans pour monter une expédition destinée à établir une colonie sur le Yarra. Mais John Pascoe Fawkner, qui était devenu un homme d'affaires à Launceston, eut la même idée. Il acheta un navire, la goélette Enterprize, qui appareilla le , avec un groupe de colons volontaires. Quand le groupe de Batman atteignit le Yarra le , ils furent consternés et furieux de découvrir les gens de Fawkner déjà en place. Les deux groupes décidèrent qu'il y avait suffisamment de terres pour tous, et quand Fawkner arriva le avec un autre groupe de colons, il fut d'accord pour diviser le terrain en parcelles et non pas de se disputer pour savoir qui était arrivé le premier. Batman et Fawkner s'installèrent tous deux dans la ville nouvelle, qui eut plusieurs noms provisoires, comme Batmania, Bearbrass, Bareport, Bareheep, Barehurp et Bareberp (en )"Batmania" Melbourne Metblogs par Neil, 13 juin 2007. Consulté le 7 juillet 2008, avant d'être officiellement baptisée Melbourne en l'honneur du Premier Ministre britannique Lord Melbourne, en .
Début de la colonisation Melbourne vit le jour sous la forme d'un rassemblement de tentes et de huttes sur les bords du Yarra, mais en l'espace de dix ans, à cause de son importance comme centre de l'économie pastorale et de la spéculation foncière, de nombreux bâtiments publics et financiers furent construits en pierre ou brique. À partir de , Melbourne devint le centre administratif du district de Port Phillip, qui faisait alors partie de la Nouvelle-Galles du Sud. Le gouvernement fut tout d'abord représenté par un magistrat de police, William Lonsdale, puis, à partir d', par un commissaire, Charles La Trobe, un homme doué, intéressé par les sciences et les arts, qui s'investit beaucoup pour faire de Melbourne une véritable cité. Sa contribution la plus durable fut de réserver de vastes espaces pour en faire des parcs publics ; aujourd'hui, on dénombre les Treasury Gardens, les Carlton Gardens, les Flagstaff Gardens, le Parc royal et les jardins botaniques. Un autre personnage important de cette époque fut Robert Hoddle, qui conçut le plan rectangulaire (le Hoddle Grid), d'après lequel la ville fut bâtie, et que suivent encore les rues du quartier central des affaires. Lors de la constitution de la ville de Melbourne, cette zone fut divisée en quatre circonscriptions : Bourke, Gipps, La Trobe et LonsdaleChronologie établie par Anne Mavric.
En 1851, la population blanche de l'ensemble du district de Port Phillip ne comptait guère plus de , bien que cette région fût devenue un centre de l'exportation de la laine australienne, et seulement d'entre elles vivaient à Melbourne. Jusqu'au boom de la construction qui suivit les ruées vers l'or, une grande partie de Melbourne était construite en bois, et presque rien de cette période n'a survécu. Deux exceptions demeurent cependant : la cathédrale St James, bâtie en 1839 au coin de Collins street et de William street, et déplacée en 1913-1914 au coin de King street et de Batman street, en face des Flagstaff Gardens, et l'église catholique St Francis, bâtie en 1841 dans Elizabeth street. Le développement des banlieues avait déjà commencé, avec la construction de coûteuses villas en bord de mer à St Kilda, et avec le développement d'un port à Williamstown. En 1848, Melbourne fut dotée d'un évêque anglican.
En , l'agitation des colons de Port Phillip porta ses fruits, le Victoria devint une colonie séparée, et La Trobe en fut son premier lieutenant-gouverneur. Quelques mois plus tard, de l'or fut découvert en plusieurs endroits de la colonie, plus particulièrement à Ballarat et à Bendigo. La ruée qui en résulta transforma radicalement le Victoria, et Melbourne en particulier.
L'arrivée d'Européens dans cette région introduisit des maladies nouvelles, qui frappèrent durement les populations aborigènes locales, dont le déclin fut précipité par de mauvais traitements, l'alcool et les maladies vénériennesIsabel Ellender and Peter Christiansen, People of the Merri Merri. The Wurundjeri in Colonial Days, Merri Creek Management Committee, 2001 . Il y eut également des conflits de frontières, comme la bataille de Yering en 1840Kath Gannaway, Important step for reconciliation Star News Group, 24 janvier 2007. Consulté le novembre 2008Isabel Ellender and Peter Christiansen, People of the Merri Merri. The Wurundjeri in Colonial Days, Merri Creek Management Committee, 2001 . En 1859, Simon Wonga s'activa pour réclamer des terres pour la population Kulin, afin qu'ils pussent s'établir, mais ses demandes restèrent vaines jusqu'en 1863, lorsque les membres survivants des Wurundjeri et d'autres locuteurs Woiwurrung furent « autorisés à occuper » la ferme de Coranderrk, près d'Healesville, et qu'ils y furent installés par la force.
La ville de la ruée vers l'or thumb|left|Carte de Melbourne, 1855. thumb|Lithographie des plans originaux du Parliament House de Melbourne. La découverte d'or provoqua un immense afflux de personnes au Victoria, la plupart d'entre elles arrivant par la mer à Melbourne. La population de la ville doubla en un an. En 1852, nouvelles arrivèrent dans la colonie, ce qui, combiné avec un très fort taux de natalité, provoqua une croissance très rapide de la population, ainsi qu'une expropriation tout aussi rapide des populations aborigènes dans les zones de l'intérieur, qui n'avaient pas encore été défrichées pour l'élevage du mouton. La population du Victoria atteignit en 1857 et en 1860. Lorsque l'or se fit plus rare, beaucoup de ces personnes échouèrent à Melbourne ou grossirent le nombre des chômeurs dans les villes autour de Ballarat et de Bendigo. Ceci créa un énorme malaise social, rendant indispensable l'ouverture des terres dans la campagne victorienne à de petits fermiers. En 1857, une « Convention de la terre » se tint à Melbourne. Plus tard, un gouvernement provisoire fut formé par des mineurs avides de terres, qui demanda une réforme agraire.