I november 1926 kunne toldvæsenet rykke ind i sin nye bygning ved Sønderborg Havns sydlige del. Siden genforeningen havde toldvæsenet været spredt over fire forskellige steder: Den lille toldbygning, der i 1856 var blevet opført ved siden af Hotel Rondel, lokaler i slottets nordvesthjørne, en barak ved dampskibsselskabets bro og nogle lokaler på jernbanestationen. Der havde længe været stor utilfredshed med dette, dels hos toldvæsenet selv, dels hos de større erhvervsvirksomheder i byen. I 1925 besluttedes det da at samle toldvæsenet i én bygning.
Den nye toldbygning tegnedes af klg. bygningsinspektør J.V. Petersen, Odense. Den var anbragt mellem Sønderbro og slottet og opførtes således, at den gamle toldstue fra 1856 indkapsledes i den østre ende. Toldforvalter Schlanbusch udtrykte stor glæde ved den hårdt tiltrængte udvidelse, der gjorde det muligt at samle al administration et sted, selv om han beklagede, at der trods alt ikke var blevet plads til alle funktioner - det havde krævet en etage til.
Der var ikke udelt tilfredshed i byen. Mange borgere kritiserede bygningen, og især var der stærk modstand mod den lyserøde farve, som blev betegnet som hæslig. Dybbøl-Posten var utilfreds med placeringen - den lå alt for tæt på slottet - og anbefalede en tæt beplantning af arealet mellem toldbygningen og slottet.
Bygningen blev toldbygning indtil 1971, men da var den for længst blevet for lille, og toldvæsenet var på ny spredt til flere steder.
I 1975 blev bygningen revet ned.
Kilde: Sønderborg i 100 år
Belejrings-Kirkegården ved Sønderborg Slot.
Da man i oktober 1925 gravede grunden op til den ny toldbygnings fundamenter, stødte man i en dybde af ca. 1 meter på forskellige menneskelige skeletter, der tilsyneladende har ligget side om side i afstand på omtrent 1 meter.
Det antages, at det drejer sig om slottets begravelsesplads fra en eller anden belejring, da faldne måtte begraves indenfor ringmuren.
Ved samme gravning fandtes en kanonkugle af tilhugget granit.