Der Architektenverein zu Berlin schrieb 1856 einen Wettbewerb für einen Neubau des Roten Rathauses aus. Keiner der sechs preisgekrönten Entwürfe, in der Königlichen Akademie der Künste am Pariser Platz ausgelegt, konnte sich durchsetzen. So wurde auch der an Hermann Philipp Wilhelm von der Hude vergebene erste Preis nicht realisiert. Hermann Friedrich Waesemann hatte an dem Wettbewerb nicht teilgenommen. Er reichte seine Entwürfe erst am 1. November ein. Nach verschiedenen Gutachten und nochmaliger Überarbeitung wurde das Projekt am 19. Juli 1860 bestätigt. Stadtarchivar Ernst Fidicin gab zum Tag der Grundsteinlegung – am 11. Juni 1861 – eine Gedenkschrift heraus.
Waesemann wurde von den Architekten Friedrich Wilhelm Otto Reißner und Bernhard Friedrich Daniel Kolscher, ein Kommilitone von W. von der Hude, unterstützt; Kolscher war hauptsächlich für die Innengestaltung des Roten Rathauses verantwortlich. Die Decken- und Dachkonstruktionen entwarf Johann Wilhelm Schwedler. Nach Fertigstellung des ersten Bauabschnittes an der Jüdenstraße tagte der Magistrat hier erstmals am 30. Juni 1865. Das Richtfest wurde am 9. November 1867 begangen; am 6. Januar 1870 fand die erste Sitzung der Stadtverordnetenversammlung im neuen Roten Rathaus statt.
Am 30. Juni 1871 legte Waesemann die “Schlussrechnung betreffend den Neubau des Roten Rathauses” vor; sie belief sich auf 2 119 546 Taler und fiel um 100.000 Taler geringer aus als die Geldsumme, die ihm bewilligt worden war.
Eine Marmorbüste H. F. Waesemanns von Otto Geyer befand sich in der Bibliothek des Rathauses; sie ging leider in den Kriegswirren verloren.