Oldenzaal was in de Middeleeuwen een belangrijke stad in Twente. Bij een stad hoorde een stadhuis. De voorloper van het stadhuis van Oldenzaal was mogelijk de kapittelzaal van de Plechelmus geweest. Tijdens opgravingen in de jaren 1960 werden er oude vroegmiddeleeuwse fundamentresten gevonden van een zwaar gefundeerd gebouw. Deze fundamentresten werden geïnterpreteerd als resten van een middeleeuwse woontoren.
Verwoesting door de Geldersen
Wanneer het huidige stadhuis precies gebouwd is als stadhuis weten we niet, maar een in de vloer van het stadhuis gevonden zandsteen met inscriptie vertelt dat in 1510 de hertog van Gelre het Oldenzaalse stadhuis verwoestte en dat het stadhuis in 1559 weer opgebouwd was. Dit stadhuis heeft tot 1837 dienst gedaan als stadhuis, gevangenis en rechtszaal. Een 19de-eeuws schilderij toont het oude stadhuis van Oldenzaal met zijn fraaie Renaissance-gevel. Het was een klein multifunctioneel stadhuis. Het had fraai betimmerde kamers en was zeker drie verdiepingen hoog.
De rechtspraak
In het stadhuis zetelde ook de rechtbank. Boven de deur van het stadhuis hing een grote walvisrib, als symbool voor de rechtspraak. Deze walvisrib is gedateerd in 1592 en heeft de volgende Latijnse inscriptie: "Kijk welke wondere zaken Neptunus voor de dag brengt. Laten wij met verwondering aanschouwen de reusachtige zeemonsters op onze kusten". In de gewelven van het stadhuis bevonden zich de gevangenissen, vier stuks met een folterkamer. Oldenzaal had de grootste gevangenis van Twente en aangezien de drost van Twente hier recht sprak, werden alle misdadigers van Twente in Oldenzaal veroordeeld.
Verbouwing en uitbreiding met classicistische gevel
Toen een hevige novemberstorm in 1834 de gevel van het stadhuis deed instorten, werd er door het stadsbestuur besloten het stadhuis te vergroten en te verbouwen. Men koos voor een classicistische uitbreiding aan de voorzijde. In het middeleeuwse achterhuis werd het pro-gymnasium gehuisvest. In 1893 kwam hier de MULO-school. Onderaan naast de trap zaten de privaten, men kon deze alleen via de buitenzijde bereiken. Toen rond 1930 de school leeg kwam te staan, werd dit gedeelte bij het stadhuis aangetrokken. Tot 1965 heeft het stadhuis dienst gedaan als gemeentehuis voor Oldenzaal.
