Oprindeligt lå byens rådhus og domhus i den samme bygning på Gammeltorv, men den nedbrændte ved den store brand i København i 1795.
Man indså, at placeringen ude midt på torvet, betød en væsentlig risiko ved brand, så man besluttede at opføre ny bygning på torvets vestside.

Bygningen blev opført 1803-1816 med C. F. Hansen (1756-1845) som arkitekt. Stilen er nyklassicistisk, som bl.a. ses på de kraftige søjler ud mod torvet.

Sammen med domhuset opførtes et nyt arresthus i Slutterigade.
I 1870’erne begyndte der at være mangel på plads i huset, så man overvejede at flytte rådhuset til en ny placering. Valget faldt på det tidligere halmtorv ved Vester Voldgade, hvor der i 1888 blev afholdt en stor industriudstilling. Det nye rådhus blev indviet i 1905.
Domhuset på Nytorv rummede også lokaler for Københavns Politi, men efter 1. Verdenskrig flyttede det til den nyopførte Københavns Politigård.