1803 wurde das Gebiet, in dem die Stadt liegt, erstmals von Europäern erkundet. 1835 siedelten sich dort rivalisierende Gruppen aus Tasmanien an und gaben ihm den Namen Port Phillip.
Als Gründer gelten John Batman und John Pascoe Fawkner. Batman war ein Repräsentant der im selben Jahr durch eine Gruppe von Geschäftsmännern aus Launceston gegründeten Port Phillip Association. Er kaufte rund 240.000 Hektar Land von den ansässigen Aborigine-Stämmen und gründete auf der Nordseite des Yarra-Flusses eine Siedlung. Im Oktober 1835 schlossen sich John Pascoe Fawkner, der im Folgenden die Siedlungsaktivitäten zielstrebig vorantrieb, eine Gruppe tasmanischer Siedler an.
Melbourne war im Gegensatz zu anderen Siedlungen im Südosten Australiens nie eine Strafkolonie, sondern wurde von Anfang an als Wohngebiet mit breiten Straßen und weitläufigen Parks geplant. Im Jahre 1837 erhielt die Stadt zu Ehren des damaligen Premierministers von Großbritannien, William Lamb, Second Viscount Melbourne, ihren heutigen Namen. Um 1840 lebten bereits über 10.000 Menschen in der Region rund um Melbourne.
1851 kam die Stadt von New South Wales zu der neu gegründeten britischen Kolonie Victoria und wurde deren Hauptstadt. Melbournes größte Wachstumsperiode begann in den frühen 1850er Jahren, als in Victoria Gold entdeckt wurde (insbesondere bei Bendigo und Ballarat). Zu dieser Zeit entwickelte sich die Stadt zum Handels- und Geschäftsszentrum der aus Übersee herbeiströmenden Goldgräber.
Ende des 19. Jahrhunderts wurde die Stadt ein wichtiger Eisenbahnknotenpunkt, ihr Hafen wurde ausgebaut, und bedeutende Industriebetriebe siedelten sich an. Nach der Gründung des Australischen Bundes im Jahre 1901 war Melbourne zeitweise Sitz der australischen Bundesregierung. 1913 wurde Canberra die neue Bundeshauptstadt, aber die Regierung des Landes zog erst 1927 dorthin um. 1956 fanden die Olympischen Sommerspiele in Melbourne statt.