Ordinance Office / Millitary Store [????-????]
This was a long building along the south side of today's Queensway, in front of where the JW Marriott is today.
An 1856 map shows a building on the site labeled "Ordinance Office":
On an 1880 map it is labeled "Military Store":
In this 1981 photo, the building is seen behind the tram:
I'm not sure if it is the same building from 1856-1981, or if it was re-developed during that time.