Vinkjelleren, Byens vinkjeller, var bygd sammen med rådstuen og oppført på Yngre Breida allmenning (Nikolaikirkeallmenning) i siste halvdel av 1200-tallet (først omtalt 1389). Den bestod av rom for utskjenkning og forsamlingslokale samt lager. Utskjenkningsrommet hadde gulv av naturheller og glasserte fliser. Byrådet stod for utskjenkningen. Etter en brann 1476 ble Vinkjelleren gjenreist 1480, og byrådet leide den ut til kjøpmennene ved Det tyske Kontor. Den ble et sentralt trekk i Kontorets virksomhet og var et møtested for både nordmenn og tyskere. Etter brann 1476 ble den gjenreist 1480. Under en ombygging på 1500-tallet fikk den en stor kamin i renessansestil, og store vinduer med blysprosser. Vinkjelleren brant 1702, og restene ble avdekket under utgravninger i 1908 og 1978–79.