Stadshuset är byggt mellan 1911–1923. När första spaden sattes i marken påbörjades också ett gigantiskt bygge med otroliga mängder arbetare igång. Bara grundläggningsarbetet var något av det mest komplicerade som gjorts i Sverige på den här tiden.
Med hjälp av dykare undersökte man botten under vattnet, eftersom det var tänkt att fundamentet så småningom skulle resa sig ur Riddarfjärdens vatten. Nästan hela Stadshuset är byggt på pålar ingjutna i armerade bottenplattor av betong, förutom själva tornet som var för tungt för att det skulle fungera. Där använde man istället kassuner och åtta enorma betongpelare som fick bära upp tornets hela tyngd på Kungsklippans förlängning under vattnet.