Toldkammerbygningen der skulle opføres 1841 blev naturligt placeret ved havnen. Den nøjagtige plads var der imidlertid nogen uenighed om. Det blev - ligeså naturligt - de højeste på stedet, amtmand Faye og toldinspektør Bülow, der fik deres vilje. Byggeriet må være sket efter nogle fortegninger fra kollegiet; andre toldbygninger som Rudkøbing og Århus havde lignende ydre. Men bygningen blev udført i entreprise af agent Werner og opført af murmester A. Gulev, under tilsyn af Faye. Vi har en tegning af indretningen optaget kort før nedrivningen. Der var to etager men ingen kælder. Dimensionerne var 20 gange 13 alen og godset kom ind fra syd (Toldbodgade) først til "pakhus og vejerbod” og derfra til ”pakhus” (mod Skolestræde). Besøgende kom ind fra havnegade ad en 5 trin høj trappe og mødte ”assistentens kontor” lige til venstre. En trappe førte op til 1. sal, hvor der var hovedkontor og ”forsal” til ”stempelsal”, der ligesom inspektørens og kontrollørens kontorer vendte ud til havnens morgensol. Når der ingen kælder var, er det egentlig lidt fantastisk at begge indgange er ad trapper (4-5 trin). Måske er det ængstelse for oversvømmelser? Eller fordi vareindgangen skal være bekvem for losning fra hestevogn - og personindgangen skal være fornem?.

Fra brandtaksationen 1857 ved vi at der var 1 hoved- og 1 stikskorsten, 5 kakkelovne til de fem kontorer og 1 locum for den nordre ende. At huset var for lille viste sig snart. Særlig uheldigt var det, når importører lod deres varer ligge ufortoldet på toldboden til de skulle bruge dem, for det medførte en sådan sammenstuvning, at det kunne knibe med at få de inderste effekter fri.

I 1870erne var det klart at en nybygning blev nødvendig. Der var ingen problemer med at få tegninger fra den kongelige bygningsinspektør for Jylland, V. Th. Walther, som havde udført andre toldbodsbygninger. Han var jævnaldrende med Herholdt (se side 14) og en nær ven af denne, således havde de delt værelse i Hamburg, da de begge havde byggearbejde i den nedbrændte by i 1840’erne. Hvor Herholdt var nyskaberen, var Walther en dygtig tegner - og han arbejdede gerne i røde mursten med en påvirkning af florentisk renæssance med raffinerede vinduer og friser, udført i formsten. Derimod var der problemer med at få en bevilling gennem folketinget her under venstres visnepolitik, og når det lod sig gøre var det en del af en studehandel mellem venstrelederen Berg og regeringen om noget nede i Kolding. Men den 14. juli 1885 kunne den tages i brug. Brandtaksationen siger: kælder: 2 rum, stue: 2 værelser og pakrum, salsetage: 7 værelser og 2 trapperum. Ialt 5 kakkelovne, fast decimalvægt, 10 gaslamper, i tårnet 1 gaslampe foruden ur og flagstang. Den var altså stort set indrettet som den gamle, blot med mere plads.

Hvor den gamle havde ligget indrettedes en gård (bag en port) og i bunden af den et lille palads til skarnkasse, 2 retirader og 1 pissoir. At der var politiske overtoner fremgik af at Højres avis kalder den byens smukkeste bygning (med tårn og med ur!); hvorimod venstreavisen i sin ”anmeldelse” skriver: "Bygningen . . er temmelig firkantet . . . dens ydre noget trykket, thi længden står ikke i det rette forhold til de øvrige dimensioner”, og iøvrigt beklager, at kun en snedker og en blikkenslager fra Thisted har fået arbejde ved opførelsen. Og man forklarer omhyggeligt (og med glæde?), hvor svært det har været at holde grundvandet ude fra kælderen. Men de gråmalede eller sølvbroncerede gaskandelabre har nu nok imponeret alle andre end de knapt 100 venstrevæl­gere i byen.