Parmi les plans conservés aux archives départementales, celui de 1856 (doc. 1) semble figurer en rose un premier projet de palais de justice, implanté dans le jardin de l'ancien couvent de célestins, face à la rue Saint-Denis (actuelle rue Victor-Hugo). Le plan de 1860 (doc. 2) est sans doute le premier projet présenté au conseil des Bâtiments civils et contesté par Jacques Hittorff. Celui de 1865 (doc. 3) donne l'implantation de l'édifice actuel et le détail d'une place-jardin à aménager à l'est, rue Saint-Denis (actuelle rue Victor-Hugo). Enfin, le plan de 1874 (doc. 4) indique les parties achevées à cette date et en rose les parties en cours d'exécution. On peut voir que la maison d'arrêt et le palais de justice sont encore installés dans les vestiges de l'ancien couvent de célestins, à l'ouest de la rue ouverte (actuelle rue Robert-de-Luzarches).

Selon J. Foucart (1989), qui fait une longue critique de l'édifice (cf. annexe), la construction d'un nouveau palais de justice, alors installé dans l'ancien couvent de célestins, est décidée en 1860 ; elle est contemporaine du projet d'ouverture de la rue Robert-de-Luzarches, dans l'axe du portail de la cathédrale. En 1861, les architectes Herbault et Daullé présentent un projet soumis au conseil des Bâtiments civils, dont le rapporteur préconise l´emploi du style Louis XIII (brique et pierre). L'année suivante, le nouveau rapporteur de la commission, Jacques Hittorff, dénonce un palais de justice aux allures d'hôtel ou de petit château, imposant une salle des pas perdus par étage, au lieu des multiples vestibules. Il suggère en outre l'emploi d'un style plus classique de façon " à appliquer aux façades une dignité architecturale qui ne permette pas de [le] confondre [...] avec une riche habitation et qui exprime mieux le caractère d'un monument dont la destinée est aussi élevée et sévère que celle d'un palais de justice". Un troisième avant-projet à portique également rejeté par Hittorff qui dénonce de plus la similitude des deux façades. Le projet définitif rehaussé de 12 à 20 mètres s'organise autour de trois immenses salles des pas perdus. La construction s'effectue en deux campagnes, l'une de 1864 à 1868, l'autre de 1874 à 1880. Suite aux nombreux vices de construction, l'architecte Herbault se donnera la mort en 1880.

Selon les recherches menées par Nathalie Mette lors de l'enquête de 1997, le palais de justice est construit sur les plans de l'architecte départemental Jean Herbault, à l'emplacement de l'ancien couvent de Célestins. En 1855, l'architecte, associé à Natalis Daullé, est chargé de dresser les plans d'un palais regroupant toutes les juridictions. Le projet examiné par Hittorff est approuvé en juillet 1864 ; il prévoit le remploi de boiseries des sculpteurs François et Charles Cressent, sont fils, réalisées entre 1702 et 1705 pour le couvent de Célestins. L'entrepreneur Leroy-Digeon est adjudicataire des travaux en 1866. La construction s'effectue en deux campagnes, l'une pour la partie est (1866-1874), la seconde pour la partie ouest (1874-1880), sous la direction de Jean Herbault après la mort de Natalis Daullé (1873). L'affaissement des planchers dans les salles aux dimensions démesurées, du à une erreur de calcul et à un mauvais choix des matériaux, nécessita leur renforcement par des colonnes de fonte et des arcs de décharge, réalisé sous la direction de l'architecte Emile Ricquier, après le suicide de Jean Herbault.