Herholdt ble utdannet tømrersvenn i 1837 og var tømrer inntil 1840. I denne perioden bodde han sammen med en eldre bror i en av Christiansborgs sidebygninger, og herfra var det utsikt til byggeplassen for Thorvaldsens Museum; han fulgte med interesse oppføringen av dette monumentale verket.
Samtidig gikk han i de ledige månedene på Kunstakademiet på kveldstid og på tegneskole om dagen; først hos G.F. Hetsch, senere hos M.G. Bindesbøll. Av den første lærte han korrekt tegning og kjennskap til den antikke stilen, av sistnevnte kjærlighet til kunsten uten hensyn til stil og respekt for en kunstners arbeide. Han fulgte med oppmerksomhet utføringen av tegningene til museet som ble omarbeidet igjen og igjen inntil de tilfredsstilte mesteren.
Fra 1841 reiste Herholdt rundt i Danmark, Norge og Nordtyskland, hvor han foretok en del oppmålinger og hadde forskjellige jobber underveis, blant annet ved oppføringen av Altona Kiel-jernbanen, men i 1845 vendte han tilbake til København for å fullføre studiene.
Herholdts første større oppgave ble Københavns Universitetsbibliotek, som han vant ved en konkurranse hvor bl.a. også Bindesbøll deltok og bygningen ble oppført 1857–61. Som motiv benyttet han kirken St. Fermo i Verona, men disse norditalienske bygningene fordret en teknikk i murstensfabrikasjonen som dengang var helt ukjent i Danmark. Herholdt fikk tak i noen eiere av mindre teglverk og fikk dem til å lage gode fasadestener, formsten og glasert sten. Dette initiativet ga teglverksindustrien et betydelig skritt fremover. Også ved å benytte en større jernkonstruksjon i bygningens indre til brannsikring, var han en foregangsmann.
Herholdt var ikke bare utøvende arkitekt, men var også lærer i Borgerlig Bygningskunst ved Polyteknisk læreanstalt (1860–75) og hans betydelige viten og en sterk følelse for det gedigne og verdige i arkitekturen dannet skole, Den Nationale Murstensskole, som ga inspirasjon for den kommende generasjon av arkitekter Hans J. Holm, H.B. Storck, J.E. GnudtzmannMartin Nyrop, og Martin Borch. Hans prinsipp var:«Se med egne øjne og ikke gennem udlandets briller! Benyt så vidt muligt landets materialer og studér den hjemlige bygningskunst i dens bedste perioder!»
Studenterforeningens bygning ved Holmens Kanal (1861-1863, revet)
Johanne Luise Heibergs villa, Rosenvængets Hovedvej 18, Rosenvænget, Østerbro, København (1862–63, veksthus bygget på i 1896 ved Valdemar Ingemann og revet 1999, interiør helt bygget om.)
M.E. Grøn & Søns varepakkhus, Holmens Kanal 7, København (1862–63, restaurert 1990–91, fredet)
21. oktober 1892 overrakte danske håndverksmestre Herholdt en kostbar minnetavle som takk for alt han i sitt lange, flittige liv hadde vært for dansk bygningskunst og dansk håndverk.