En 1549, deux étages étaient construits lorsque, les travaux s'arrêtèrent soudain; un artiste Italien, Dominique Boccardos dit Cortone, proposa au roi Henri II des modifications au plan primitif qui nécessitèrent de nouvelles dispositions. M. de Guilhermy n'est pas d'accord sur ce point avec la plupart des historiens ; il prétend que le plan original fut conçu par Cortone et exécuté par lui ; quoi qu'il en soit, les travaux marchèrent bien lentement, sans cesse interrompus par les troubles civils qui marquèrent les règnes de Charles IX et d'Henri III. En 1606, l'architecte Marin de la Vallée acheva le gros œuvre ; en 1608, la grande salle fut terminée, le pavillon du nord commencé et la tour octogone de l'horloge élevée sur le comble.

Le pavillon méridional avait été construit sous Henri II, celui du nord ne fut achevé que sous Louis XIII en 1628.

A cette époque l'hôtel de ville se composait d'un, corps de bâtiments central formant façade au couchant, flanqué de deux pavillons carrés et de constructions extérieures entourant une tour quadrangulaire, décorée de portiques d'un style très élégant.

Des divers corps de logis , celui qui occupait le centre de la façade se composait d'un rez-de-chaussée et d'un étage supérieur ; les deux pavillons d'angle avaient un étage de plus ; cette façade était coupée de fenêtres carrées ou cintrées divisées en croix par des meneaux de pierre ; des colonnes cannelées d'ordre composite, s'ajustaient entre les baies du rez-de-chaussée et allaient se relier par des consoles renversées à des niches placées entre les treize fenêtres du premier étage. Sous les niches, des culs de lampe historiés présentaient des génies, des têtes d'anges, le vaisseau des armoiries de la ville, des H couronnés. Au-dessus de la porte était placée une figure équestre de Henri IV par Pierre Biard; fort dégradée lors de la fronde, mutilée et enlevée en 1793, cette figure fut remplacée en 1815 par une statue en bronze. Les combles très élevés, étaient percés au-dessus de la corniche de grandes fenêtres de pierre ornées d'enroulements et de figures de femmes tenant des palmes. Au milieu de la façade un attique contenait le pavillon de l'horloge environné de statues de pierre : la Seine, la Marne, la force, la Justice et la ville de Paris ; à l'entablement, deux génies accompagnaient un écusson aux armes municipales — de gueules au vaisseau équipé d'argent, sur une onde du même, au chef cousu d'azur, semé de fleurs de lis d'or, couronne murale à quatre tours. Devise ; fluctuat nec mergitur, (il flotte mais ne sombre pas).