De Brooklyn Borough Hall is ontworpen in 1835 door de architect Gamaliel King en werd gebouwd onder toezicht van Stephen Haynes. Het werd als Kings County Courthouse voltooid in 1849 en werd vanaf toen gebruikt als stadhuis van Brooklyn. In januari 1898 werd deze onafhankelijke stad geannexeerd door New York en werd het een van de boroughs (stadsdelen) daarvan. De Borough Hall is het oudste publieke gebouw van Brooklyn. Het kantoor van de Brooklyn Borough President is er gevestigd.
De bouw van het stadhuis van Brooklyn begon in 1845 en duurde tot 1849. Het Kings County Courthouse was gebouwd in 1868, waardoor het gebied (later bekend als Downtown Brooklyn) het bestuurlijke centrum werd en een druk commercieel gebied. In de jaren 1940, werd het Kings County Courthouse met andere gebouwen in het noorden vervangen door een aantal rechtbanken en een plein voor de Borough Hall.
Door een brand op 26 februari 1895 werden de koepel en de bovenverdiepingen beschadigd. Daardoor hing er hierna voor 85 jaar een vlag boven het gebouw. Tot het jaar 1980, toen werd het gebouw gerestaureerd en werd het beeld van Vrouwe Justitia weer op de nieuwe koepel geplaatst.