Omstreeks het midden van de vijftiende eeuw kregen de inwoners van Middelburg behoefte aan een nieuw ‘stedehuus’. Eerdere stadhuizen zouden aan het begin van de Lange Delft en in de Lange Noordstraat hebben gestaan

De bouw van het nieuwe raadhuis ving aan op 21 april 1452 met het leggen van de eerste steen voor het Vleeschhuis en van de hal.  Het raadhuis was niet alleen het bestuurscentrum van de stad, maar ook vleeshal en lakenhal. Dit paste geheel in de middeleeuwse (Vlaamse) traditie. De bouwmeesters waren dan ook Vlamingen. Aan het Middelburgse stadhuis werkten maar liefst acht leden van het bouwmeestersgeslacht Keldermans uit Mechelen, verspreid over zeven generaties. Zij waren architect, opzichter, steenhouwer en leverancier van bouwmaterialen.

In 1458 was het gedeelte aan de Markt gereed. Op 14 maart van dat jaar kon het stadsbestuur er voor het eerst vergaderen. Het stadhuis is gebouwd in de stijl van de late Vlaams-Brabantse gotiek. De gevel van het stadhuis is dan ook rijk versierd.

Graven en gravinnen
Omstreeks 1506 begon een nieuwe bouwcampagne. De voltooiing van de stadhuistoren in 1521 vormde de afsluiting daarvan. De topgevels aan de kant van de Noordstraat en de Markt kwamen in 1512 gereed. In deze periode werden in de voorgevel ook beelden aangebracht. Het waren beelden van de graven en gravinnen die over Zeeland hadden geregeerd. De steenhouwer Michiel Ywijnszoon uit Mechelen leverde deze ‘steenen persoenagien’. Ze werden in kisten naar Middelburg vervoerd, in de jaren 1514 tot 1518 stuurt hij er ieder jaar vijf.

De beelden werden in Middelburg vóór hun plaatsing gepolychromeerd (= beschilderd), en wel in tamelijk felle kleuren Vooral de kleuren rood en blauw kwamen voor, de regalia (kronen e.d.) werden verguld. Die felle kleuren zouden nu een vreemde indruk op ons maken. De historische werkelijkheid is echter veel kleurrijker geweest dan we vaak denken.

Op 17 mei 1940 voltrok zich een ramp toen de binnenstad van Middelburg ten prooi viel aan een grote brand ten gevolge van het oorlogsgeweld. Het stadhuis werd zwaar beschadigd. Vrijwel het hele inpandige gedeelte van het gebouw ging toen verloren. Een grote restauratiecampagne volgde. Die duurde tot diep in de twintigste eeuw. Men besloot het oude stadhuis niet te reconstrueren, maar de gotische gevels te herstellen en een nieuwbouwgedeelte in aangepaste stijl toe te voegen. Op 18 augustus 1950 kon het gebouw met een feestelijke bijeenkomst in de Burgerzaal weer in gebruik worden genomen. Koningin Juliana verrichtte op die dag de opening.

Het gebouw wordt o.m. gebruikt als trouw-locatie en voor formele bijeenkomsten. Het is sinds 2003 hoofdzakelijk in gebruik bij de University College Roosevelt.