Lekwummen is the language spoken by the native people who lived where Victoria is today. The Songhees and Esquimalt First Nations are part of this group. Prior to the 1770s they were very numerous in villages all around the harbour, but severe depopulation occurred due to diseases such as smallpox which came up from the Spanish in Mexico in the late 1700s. The Lekwummen word for the area around Bastion Square was kuo-sing-elas which means “place of strong fibre” – a reference to the Pacific willow which grew thickly there. It is likely that villages were located at or near Bastion Square, and burial sites would have been dotted along much of the shoreline. Camas was a bulb cultivated by the Lekwummen, and there were probably camas beds in the area, too.
No First Nations were living in the immediate area when Fort Victoria was built. The nearest villages were at Cadboro Bay and Esquimalt Harbour. However, when the fort was built, the Songhees from Cadboro Bay moved to Victoria Harbour and a group of Clallam came from the Olympic Peninsula and for a while were located close to the fort, probably where the foot of Bastion Square is today, at Wharf Street.