Melbourne a été fondée en 1835, sous le règne du roi Guillaume IV avec l'arrivée de la goélette Enterprize près de l'emplacement actuel du Quai de la Reine (Queen's Wharf), comme point de colonisation sauvage, indépendamment du gouvernement de Nouvelle-Galles du Sud. Contrairement à d'autres villes d'Australie, Melbourne n'est pas une ville créée par les officiels mais plutôt par la clairvoyance de colons de Tasmanie[réf. souhaitée].
Située sur le territoire de la Nouvelle-Galles du Sud, les affaires de la ville ont été gérées directement par le Parlement de Nouvelle-Galles du Sud. Avec la croissance de la colonie, les habitants ont demandé une plus grande autonomie pour gérer leurs propres affaires. Le , Melbourne est devenue officiellement une ville (Town).
La ville de Melbourne a été élevée au rang de Ville (City) par lettre patente de la reine Victoria en date du . Le lettre patente créait également le diocèse anglican de Melbourne.
