Het stadhuis (Markt 1) is een U-vormig gebouw met een belfort-achtige toren voorzien van een achtzijdige lantaarn. Het wordt beschouwd als een hoogtepunt van de profane laat-gotische architectuur in Nederland.
In 1452 begon men onder leiding van Andries en Mattheus Keldermans aan een L-vormig gebouw op de hoek van de Markt en de Lange Noordstraat. In de binnenhoek verrees een forse toren, op korte afstand daarvan een traptoren en op de buitenhoek een eveneens als traptoren dienstdoende achtzijdige erkertoren (‘de Choertoren’).
In 1460 waren de buitengevels gereed, voorzien van dubbele beeldnissen tussen de met laat-gotische traceringen versierde vensters. Gelijktijdig werd gewerkt aan de Vleeshal achter de drie meest linkse traveeën, die men vooralsnog tot de diepte van de traptoren aan de achterzijde optrok.
De ingangen van het stadhuis bevonden zich zowel aan de Lange Noordstraat als in de brede travee naast de Vleeshal. In 1492 maakte een brand herstelwerkzaamheden nodig en kwam er boven de Vleeshal een Lakenhal.In 1506 begon een nieuwe bouwcampagne onder leiding van Andries' zoon, Anthonis Keldermans, die in 1512 op zijn beurt werd opgevolgd door zijn zoon Rombout. De toren kreeg in 1506-'11 een achtzijdige lantaarn, die met luchtbogen werd verbonden met rijzige, steunbeerachtige hoekpilaren. Mogelijk beoogde men in eerste instantie een opengewerkte stenen spits als bekroning, maar uiteindelijk kwam in 1560 de kenmerkende helmvormige bekroning gereed. In de toren bevinden zich een door Medardus Waghevens gegoten klok (1527), een kopie van het uit 1525 daterende uurwerk met wijzerplaten en een speelwerk met ruiters en hellebaardiers. De bekroning van de Choertoren en de rijk bewerkte topgevel aan de Noordstraat werden in 1511 gerealiseerd. Aan de nog iets rijkere topgevel van de Vleeshal (en ingang) aan de Markt begon het werk in 1513, evenals aan de verlenging en overwelving van die hal.
In 1514-'15 werd gewerkt aan de kap met tongewelf van de bovengelegen Lakenhal. Vervolgens heeft men het bouwdeel met de Vleeshal en Lakenhal in zijn geheel nogmaals achterwaarts verlengd, waarmee deze bouwfase rond 1520 werd voltooid. In de beeldnissen aan de voorzijde kwamen in 1514-'18 beelden van de graven van Holland en Zeeland te staan, gemaakt door Michiel Ywijnsz uit Mechelen.
Met het ontstaan van de huidige Markt als gevolg van de afbraak van de Westermonsterkerk (1575) kreeg het stadhuis in 1613 de huidige ingang. Het lage hardstenen bordes met in de borstwering het oude wapen van Middelburg werd in 1756 toegevoegd naar plannen van Jan de Munck. De Vleeshal voorzag men in 1729 van een zonnewijzer, eveneens vervaardigd door Jan de Munck (verwijderd 1910, herplaatst 1995). Van zijn hand is ook de hardstenen pomp aan de achterzijde. Aan de Lange Noordstraat verrees in 1780-'84 een stadhuisuitbreiding in strenge Lodewijk XVI-stijl naar plannen van Coenraad Kaijser.
Het stadhuis werd tussen 1881 en 1918 in fasen gerestaureerd onder leiding van L.C. Hezemans en P.J.H. Cuypers. Daarbij verving men de gevelbeelden door kopieën van atelier Cuypers. In de geveltop van de Vleeshal werd in 1910 een beeld van koningin Wilhelmina met haar pasgeboren dochter Juliana geplaatst. De Choertoren werd versierd met beelden van de Bourgondische hertogen: Maximiliaan (1925) door N. van der Schaft, Maria van Bourgondië (1928) en Karel de Stoute (1933) door L.
Zijl, Karel V (1934-'36) en Philips de Stoute door H.J. Etienne. Bij het bombardement in 1940 brandde het raadhuis geheel uit. Kort daarop werd de gevel van de 18de-eeuwse uitbreiding neergehaald. De restauratie in oorspronkelijke vorm vanaf 1941 vond in 1968 zijn voltooiing. Ter plaatse van de 18de-eeuwse uitbreiding en in het verlengde daarvan verrees in 1946-'50 naar plannen van A. van der Steur een nieuw bouwdeel en aan de westzijde een secretarievleugel, onderling verbonden door een arcade.
Inwendig is de oorspronkelijke indeling van het gebouw gehandhaafd of teruggebracht waar latere verbouwingen hadden plaatsgevonden. Dit laatste geldt met name voor de opnieuw van een houten tongewelf voorziene Lakenhal (nu Burgerzaal). De stenen gewelven boven de trap, in de torenkamer en in de Vleeshal zijn gedeeltelijk nog oorspronkelijk. Ter vervanging van de verbrande inventaris zijn sinds 1940 diverse meubelen en interieuronderdelen aangekocht, zoals een hardstenen gotische schouw (1549) voor de Trouwzaal. In de Raadzaal bevinden zich een groot gebeeldhouwd stadswapen uit de vroegere 18de-eeuwse uitbreiding, en in de kamer daarnaast een 17de-eeuwse schouw en een 18de-eeuwse betimmering afkomstig uit Groningen.
