Le Victoria a été le lieu de vie de nombreuses nations autochtones qui ont occupé la région pendant des dizaines de milliers d'années. Selon Gary Presland les Aborigènes ont vécu au Victoria pendant environ 40 000 ans, menant une existence semi-nomade vivant de la pêche, de la chasse, de la cueillette et de l'élevage d'anguilles.