Københavns første brandvæsen blev grundlagt af kong Christian 5. 9. juli 1687. Med lov at 18. maj 1868 blev Københavns Brandvæsen oprettet som kommunal institution pr. 1. august 1870.[2] På det tidspunkt var brandstationen i den tidligere Sankt Nicolai Kirke blevet forældet, og det blev derfor besluttet at opføre en ny til formålet på området for den tidligere Vestervold. Københavns Befæstning var blevet sløjfet i årene forinden, og det frigivne område blev nu benyttet til en række store offentlige byggeprojekter.
Den nyligt udnævnte stadsarkitekt Ludvig Fenger blev sat i spidsen for projektet.[3] Opførelsen begyndte i 1889, og den nye hovedbrandstation blev taget i brug 30. april 1892. På den tid var rådhuset endnu ikke bygget, og der var derfor frit udsyn til Halmtorvet, der lå hvor Rådhuspladsen nu ligger. Hovedbrandstationen blev opført i historisk stil inspireret af middelalderlige norditalienske borge med krenelerede gavle, spidsbueformede porte og et tårn.[3] Tårnet blev benyttet til træning med sikkerhedsnet og høje brandstiger.[3]